ICAOR’14 ABSTRACTS

6TH INTERNATIONAL CONFERENCE ON APPLIED OPERATIONAL RESEARCH

29-31 JULY 2014, VANCOUVER, BC CANADA


THE HEALTHCARE SECTOR NEEDS MORE OPERATIONAL RESEARCH

Tomas Eric Nordlander

SINTEF ICT, Department of Applied Mathematics, Oslo, Norway

Tomas.Nordlander@sintef.no

Abstract. More efficient use of resources and improved quality of services is needed in the health care sector, in order to meet the challenges of aging populations coupled with rising quality expectations due to technological advances and desire to cap or reduce budgets. In healthcare, complex decisions at strategic, tactical, and operational levels are coupled across organizational boundaries, with interdependency between plans that share many of the same resources and infrastructure. Decision support tools from Operations Research have for decades been successfully applied to complex resource management problems in other industries. While such tools are needed in the health sector, they are no panacea but maybe one of the most promising approach to ease their strain. A wide-spread application of such tools will increased efficiency at hospitals and patients will experience more streamlined coordination of activities, improved predictability and regularity—getting a higher service levels and ultimately better quality of health care services.


APPROXIMATED DYNAMIC PROGRAMMING ALGORITHMS WITH VARIABLE NEIGHBOURHOOD SEARCH FOR REFORMED DYNAMIC QUADRATIC ASSIGNMENT PROBLEMS

Pongchanun Luangpaiboon 1, Sirirat Muenvanichakul 2 and Peerayuth Charnsethikul 2

1 Industrial Statistics and Operational Research Unit (ISO-RU), Dept of Industrial Engineering, Faculty of Engineering, Thammasat University, Pathumthani, Thailand

lpongch@engr.tu.ac.th

2 Dept of Industrial Engineering, Faculty of Engineering, Kasersart University, Bangkok, Thailand

sirirat.m@ku.ac.th

Abstract. When determining the optimal solution of the dynamic quadratic assignment problem (DQAP) it is extremely difficult since it is the NP hard problem. The reformed dynamic quadratic assignment problem (RDQAP) has been reformulated and applied in two alternatives of linearised and logic-based models after proving the model equivalence. This study follows the former and introduces the hybridisation of the conventional dynamic programming algorithm with the meta-heuristics of bee colony optimisation (ADPA-I) and simulated annealing (ADPA-II) algorithms called the approximated dynamic programming algorithms (ADPA).  In order to improve quality of solutions the variable neighbourhood search is also included with given initial solutions from the ADPA. In the context of ADPA, the searching procedures are incomplete as in the original DPA. For each period, a set of best solutions provided by metaheuristics is determined as the initial solution set. The number of all possible solutions is the product of initial solution set of all periods. Numerical results explain the superior quality of the ADPA-I obtained solutions when compared.


IDENTIFYING AIRCRAFT AND PERSONNEL NEEDS TO MEET ON-STATION PATROL REQUIREMENTS

F-A Bourque 1,*, R Mirshak 1, PL Massel 1, BU Nguyen 1 and Major JCW Ansell 2

1 Centre for Operational Research and Analysis, Defence Research and Development Canada, Department of National Defence, Ottawa, ON, Canada

{alex.bourque, ramzi.mirshak, paul.massel, bao.nguyen}@drdc-rddc.gc.ca

2 Directorate of Naval Strategy, Department of National Defence, Ottawa, ON, Canada

bill.ansell@forces.gc.ca

Abstract. Determining the required number of aircraft and personnel to maintain a given presence on station is a common and important problem in military contexts.  In this paper, the proposed approach consists of finding schedules for multiple aircraft that meet the on-station requirement while minimizing the number of aircraft and crews required. Specifically, after discussing the schedule for a single aircraft, an integer program for the multiple aircraft case is formulated and presented. To capture the effect of unplanned maintenance on the overall number of required aircraft, a parameterized serviceability model is also introduced. As illustrated by a case study, this easy to implement methodology is able to provide quick and insightful results to the decision makers.


BLOOD SUPPLY CHAIN WITH INSUFFICIENT SUPPLY:  A CASE STUDY OF LOCATION AND ROUTING IN THAILAND

Pornpimol Chaiwuttisak, Honora Smith, Yue Wu and Chris Potts

University of Southampton, Highfield, Southampton, United Kingdom

pc12g09@soton.ac.uk

Abstract. Decision making on facility locations for blood services and blood distribution plan has an impact on the efficiency of blood supply chain and logistics systems. In the blood supply chain operated by the Thai Red Cross Society (TRCS), problems are faced with amounts of blood collected in different provinces of Thailand being insufficient to meet demand. A proposal has been made to extend this network of blood centres using low-cost collection and distribution centres. Increasing numbers of fixed collection sites can improve access for donors. In addition, some facilities can perform preparation and storage for blood that hospitals can receive directly. Selecting sites for these two types of facility within a limited investment budget informs the strategic plan of this non-profit organisation. Furthermore, we consider the blood delivery problem to hospitals under variable and insufficient supplies of blood. Hospitals are assigned either to fixed routes or variable routes according to their location. Blood is supplied weekly to hospitals in the fixed route, while the frequencies of blood distribution to hospitals in the variable routes changes with the quantity of blood available daily. In the paper, we present a novel binary integer programming model for this location-allocation problem based on objectives of improving supply of blood products while reducing costs of transportation.  Furthermore, we propose an online system for updating the delivery schedule over the planning horizon. Different policies for allocation and routing are compared, with a case study in northern Thailand. Computational results are reported, using real life data that are of practical importance to decision makers.


DETERMINING OPTIMAL OSMOTIC DRYING PARAMETERS FOR PAPAYA USING THE FIREFLY ALGORITHM

Julian Scott Yeomans 1 and Xin-She Yang 2

1 OMIS Area, Schulich School of Business, York University, Toronto, ON, Canada

syeomans@schulich.yorku.ca

2 School of Science and Technology, Middlesex University, London, UK

xy227@cam.ac.uk

Abstract. This study employs a Firefly Algorithm (FA) to determine the optimal osmotic dehydration parameters for papaya. The functional form of the osmotic dehydration model is established via a standard response surface technique. The format of the resulting optimization model to be solved is a non-linear goal programming problem. While various alternate solution approaches are possible, an FA-driven procedure is employed. For optimization purposes, it has been demonstrated that the FA is more computationally efficient than other such commonly-used metaheuristics as genetic algorithms, simulated annealing, and enhanced particle swarm optimization. Hence, the FA approach is a very computationally efficient procedure. It can be shown that the resulting solution determined for the osmotic process parameters is superior to those from all previous approaches.


AN ANALYTICAL FRAMEWORK WITH A NETWORK-BASED OPTIMIZATION MODEL FOR RESCHEDULING A DELAY CONTAINERSHIP

Hua-An Lu

Department of Shipping and Transportation Management,

National Taiwan Ocean University, Keelung, Taiwan

halu@ntou.edu.tw

Abstract. Schedule reliability is one of the advantages that container liner shipping can play an important role in the global logistics system. However, some environment conditions and special situations will occasionally cause ship delays. This research introduces some viable strategies that can be applied to get a delay containership back on track in actual practice. An analytical framework with a network-based optimization model is proposed herein to assess the possible alternatives for counteracting delays at various target ports. Analysis results for a short sea service present the relationships between extra costs and countermeasures.


A HEURISTIC APPROACH FOR AN INVENTORY ROUTING PROBLEM WITH BACKORDER DECISIONS

Stella Sofianopoulou

Department of Industrial Management & Technology, University of Piraeus, Greece

sofianop@unipi.gr

Abstract. A multi-period inventory-routing problem is considered where a vendor serves multiple geographically dispersed customers who receive units of a single product from a depot, with adequate supply, using a capacitated vehicle. The class of problems arising from the combination of routing and inventory management decisions is known as the inventory routing problem (IRP). In this category of problems, the inventory routing problem with backorders (IRPB) deals with determining inventory levels when backorders are allowed. The aim is to minimize the total cost for the planning period, comprising of holding cost, transportation and backorder penalty cost while ensuring that inventory level capacity constraints are not violated. An Integer Programming model is first developed to provide an accurate description of the problem and then a Genetic Algorithm (GA) with suitably designed genetic operators is employed in order to obtain near optimal solutions. Computational results are presented to demonstrate the effectiveness of the proposed procedure.


A GENERALIZED ADDITIVE NEURAL NETWORK APPLICATION IN INFORMATION SECURITY

Tiny du Toit and Hennie Kruger

North-West University, Potchefstroom Campus, Potchefstroom, South Africa

{tiny.dutoit, hennie.kruger}@nwu.ac.za

Abstract. Traditionally spam has been considered as an inconvenience requiring workers to sift through and delete large numbers of e-mail messages per day. However, new developments and the Internet have dramatically transformed the world and over the last number of years a situation has been reached where inboxes have been flooded with unsolicited messages. This has caused spam to evolve into a serious security risk with prominent threats such as spreading of viruses, server problems, productivity threats, hacking and phishing etc. To combat these and other related threats, efficient security controls such as spam filters, should be implemented. In this paper the use of a Generalized Additive Neural Network (GANN), as a spam filter, is investigated. A GANN is a novel neural network implementation of a Generalized Additive Model and offers a number of advantages compared to neural networks in general. The performance of the GANN is assessed on three publicly available spam corpora and results, based on a specific classification performance measure, are presented. The results showed that the GANN classifier produces very accurate results and may outperform other techniques in the literature by a large margin.


REVERSE LOGISTICS DECISION MAKING FOR MODULAR PRODUCTS: THE IMPACT OF SUPPLY CHAIN STRATEGIES

Thomas Nowak 1, Fuminori Toyasaki 2, Tina Wakolbinger 1 and David Ng 3

1 Institute for Transport and Logistics Management,

Vienna University of Economics and Business, Vienna, Austria

{thomas.nowak, tina.wakolbinger}@wu.ac.at

2 School of Administrative Studies, York University, Toronto, Canada

toyasaki@yorku.ca

3 Department of Economics, York University, Toronto, Canada

davidjng@yorku.ca

Abstract. The importance of product modularity in mitigating negative product-related environmental effects has been widely recognized in practice and in research. This study analyzes how a company’s supply chain strategy is linked with a product’s optimal level of modularity and how this affects efficient reverse logistics decision making. We address this problem by formulating two optimization problems; one for a company adopting a push and one for a company adopting a pull supply chain strategy.


A DIET EXPERT SYSTEM UTILIZING LINEAR PROGRAMMING MODELS IN A RULE-BASED INFERENCE ENGINE

Annette van der Merwe, Hennie Krüger and Tjaart Steyn

North-West University, Potchefstroom Campus, Potchefstroom, South Africa

{annette.vandermerwe, hennie.kruger, tjaart.steyn}@nwu.ac.za

Abstract. Linear programming is commonly used for solving complex problems in various fields, such as dietetics. Expert systems use expertise and inference procedures to solve problems that require advanced expert knowledge and are also applied to health related problems. Over the years many variations and facets of the diet problem and other related problems have been solved by means of linear programming techniques as well as expert systems. In this research, an expert system was created for the purpose of solving multiple facets of the diet problem, by creating a rule-based inference engine consisting of goal programming- and multi-objective linear programming models. The program was successfully applied to case studies specific to South African teenage girls, which were obtained through the knowledge acquisition phase. The resulting system compiles an eating-plan for a girl that conforms to the nutritional requirements of a healthy diet, includes the personal food preferences of the girl, and consists of food items that result in the lowest total cost. The system also allows prioritization of the food preference and least cost factors by means of weighted priorities.


KALMAN-FILTERING FORMULATION DETAILS FOR DYNAMIC OD PASSENGER MATRIX ESTIMATION

Lídia Montero, Esteve Codina and Jaume Barceló

Department of Statistics and Operations Research,

Barcelona TECH-UPC, Carrer Jordi Girona 1-3  08034 Barcelona, Spain

{lidia.montero, esteve.codina, jaume.barcelo}@upc.edu

Abstract. In this paper, we describe how to estimate time-sliced origin-destination (OD) matrices for passengers in a public transport network based on counts of ICT (Intelligent Communication Technology) devices carried by passengers at equipped transit-stops. The transit assignment framework is based on optimal strategy, which determines the subset of paths related to the optimal strategies between all OD pairs for the whole horizon of study. Details are provided on how to build the involved equations in a linear Kalman filtering model formulation, which is defined by the authors for a toy network that is proposed to validate the approach.


DETERMINING FLEET SIZE FOR A CANADIAN MARITIME PATROL AIRCRAFT

Richard McCourt 1,*, Sean Bourdon 1 and Matthew MacLeod 2

1 Defence Research and Development Canada,

Centre for Operational Research and Analysis, Ottawa, Canada

{richard.mccourt, sean.bourdon}@drdc-rddc.gc.ca

2 Defence Research and Development Canada,

Centre for Operational Research and Analysis, Halifax, Canada

matthew.macleod3@forces.gc.ca

Abstract. Maintaining the ability to continuously track vessels in a maritime area of responsibility involves a mixture of factors relating to the performance of the aircraft, its sensor systems and the operators on board. This paper presents a series of simplifying assumptions and equations for considering trade-offs between three of the most important of these factors: aircraft speed, endurance and fleet size. The paper briefly presents the results obtained for a life-extended fleet of Canadian Maritime Patrol Aircraft, while also allowing the consideration of requirements for its replacement.


HEURISTICS FOR SINGLE MACHINE SCHEDULING UNDER COMPETITION TO MINIMIZE TOTAL WEIGHTED COMPLETION TIME AND MAKESPAN OBJECTIVES

Yuvraj Gajpal 1,*, Alok Dua 1 and Shesh Narayan Sahu 2

1 Asper School of Business, University of Manitoba, Winnipeg, Manitoba, R3T5V4, Canada

{yuvraj.gajpal, duaa}@umanitoba.ca

2 National Institute of Technology, Agartala

Department of Computer Science and Engineering, Tripura, 799055, India

Abstract. This paper considers a single machine scheduling problem, where two agents compete for the use of a single processing resource. Each of the agents needs to process a set of jobs with the common resource to optimize their own objective function which depends on the completion time of its own jobs. The goal is to minimize the total weighted completion time of first agent subject to an upper bound on the makespan of the second agent. The problem is binary NP-hard. We propose three simple heuristic for the problem. These heuristics are based on shortest processing time rule, highest weight first rule and weighted shortest process time first rule. Numerical experiment is performed on randomly generated problem instances. Heuristic performances are evaluated by comparing it with the exact solution.


A SIMPLIFIED MODEL FOR SCHEDULING SERVICES ON AUXILIARY BUS LINES

E. Codina and L. Montero

Statistics and Operations Research Department, Universitat Politècnica de Catalunya,

Campus Nord, Building C5, 08034, Barcelona, Spain

{esteve.codina, lidia.montero}@upc.edu

Abstract. In this paper, a mathematical programming based model is described to assist with the schedule of services for a set of auxiliary bus lines that operate alleviating a disruption of the regular transportation system during a given time period. In contrast to other models, considered static, service schedules are set taking into account demand fluctuations that may happen in that time period. Passenger flows are represented with a multi-commodity structure and disseminate through paths on a diachronic capacitated network which lead them to their destination in the shortest time taking into account the available capacities of the bus units. The model permits to accommodate the schedules of the auxiliary bus lines in order to enhance transfers and to minimize total travel time. The model assumes that operational times at bus stops are constant and that buses do not queue at stops. The solution method can be considered an heuristic that combines searches along subgradient's projected directions with a pattern search based method for constrained optimization.


PRICING, PRODUCT QUALITY, AND RETAIL SERVICE IN A THREE-ECHELON SUPPLY CHAIN

Gerhard Aust

TU Dresden, Fakultaet Wirtschaftswissenschaften, 01062 Dresden, Germany

gerhard.aust@tu-dresden.de

Abstract. This paper proposes a model of a three-echelon supply chain consisting of one supplier, one manufacturer, and one retailer, who serve customer demand that is sensitive to retail price, product quality, and retail service. By means of game theory, the firms’ optimal strategies regarding margins, quality level, and service level are determined analytically for three different scenarios: (a) a symmetrical distribution of power within the supply chain (Nash game); (b) a dominant manufacturer (Manufacturer Stackelberg game); (c) a joint profit maximization of the firms (Co-operation game). The solutions are analyzed on the base of a first numerical example, which proves that the presented model yields logically consistent results.


FROM MAXPLUS ALGEBRA TO GENERAL LOWER BOUNDS FOR THE TOTAL WEIGHTED COMPLETION TIME IN FLOWSHOP SCHEDULING PROBLEMS

Nhat-Vinh Vo and Christophe Lenté

Université François-Rabelais de Tours,

CNRS, LI EA 6300, OC ERL CNRS 6305, Tours, France

{nhat.vo, christophe.lente}@univ-tours.fr

Abstract. The flowshop scheduling problem has been largely studied for 60 years. As a criterion, the total weighted completion time reflects the total weighted waiting time of all customers. There have not been many studies about this criterion and they are limited in the number of machines or constraints. MaxPlus algebra is also applied to the scheduling theory but the literature focuses on some concrete constraints. Therefore, this study addresses a general permutation flowshop problem, with several additional constraints such as delays, blocking or setup times, to elaborate on lower bounds for the total weighted completion time. These lower bounds imply solving a Traveling Salesman Problem. The principle, based on a MaxPlus modeling of flowshop problems, is developed and experimental results are presented.


A MATHEMATICAL PROGRAMMING APPROACH FOR SOLVING THE PROBLEM OF FIXING PRICES AND AUGMENTING CAPACITY FOR TWO COMPETING SUPPLIERS

Gaytán Juan 1, García Marco 2 and Arroyo Pilar 3

1 Facultad de Ingeniería, Universidad Autónoma del Estado de México. Toluca, Mexico. Mexico

jgi@uaemex.mx

2 Escuela de Ingeniería, Tecnológico de Monterrey campus Morelia. Michoacan. Mexico

3 Escuela de Ingeniería, Tecnológico de Monterrey campus Toluca. Toluca, México. Mexico

pilar.arroyo@itesm.mx

Abstract. The decision to produce internally or outsource the manufacturing of certain goods is critical because of its effects on the utilized capacity, the production costs, the quality of products and the customer service. A bad performance of external suppliers represents a potential risk for an organization; however the internal production of low-value products involves the use of resources (physical and human) that may be used to manufacture products of higher value. Original Equipment Manufacturers (OEM) in the automotive sector need to identify reliable suppliers to who outsource the manufacturing of parts and components. In the case these suppliers do not have enough capacity to produce all the goods demanded, the OEMs may incentive them to invest in additional capacity by offering to increase the volume of production subcontracted.


SOLVING THE GREEN CAPACITATED VEHICLE ROUTING PROBLEM USING A TABU SEARCH ALGORITHM

Sergio Úbeda 1, Javier Faulin 1, Adrián Serrano 1 and Francisco J Arcelus 2

1 Department of Statistics and Operations Research. Public University of Navarre, Pamplona, Spain

{sergio.ubeda, javier.faulin}@unavarra.es

2 Department of Business Administration. University of New Brunswick, Fredericton, Canada

arcelus@unb.ca

Abstract. This paper analyses how the tabu search can be successfully applied to solve the Green Capacitated Vehicle Routing Problems- GCVRP. This kind of problems has been described as the classical Capacitated VRP with a criterion of environmental emissions minimisation. This criterion is based on the calculation of carbon dioxide emissions from mobile sources, which is highly dependent on several factors such as speed, weather conditions, load and distance. A case study is given to show how green routes can be obtained and to analyze whether those routes also meet the efficiency objectives or not. The results show that a tabu search approach adapts the environmental criterion better than other procedures and also produces routes which are distance effective and environmental-friendly.


A TRANSPORTATION BRANCH AND BOUND ALGORITHM FOR SOLVING THE GENERALIZED ASSIGNMENT PROBLEM

Elias Munapo

Graduate School of Business and Leadership, University of KwaZulu-Natal,

Westville Campus, Durban, South Africa

munapoe@ukzn.ac.za

Abstract. This paper presents a transportation branch and bound algorithm for solving the generalized assignment problem. This is a branch and bound technique in which the sub-problems are solved by the available efficient transportation techniques rather than the usual simplex based approaches. A technique for selecting branching variables that minimizes the number of sub-problems is also presented.


HEURISTIC SCHEMES FOR THE EFFICIENT UTILIZATION OF 3D PRINTING STEREOLITHOGRAPHY APPARATUS

Vassilios Canellidis, John Giannatsis and Vassilis Dedoussis

University of Piraeus 80 Karaoli & Dimitriou str., 18534 Piraeus, Greece

{bcanell, ggia, vdedo}@unipi.gr

Abstract. 3D Printing (3DP) technologies are increasingly being employed for the production of consumer products and mechanical components in the manufacturing sector, because of the advantages they exhibit as far as fabrication speed and flexibility are considered. This shift of focus in the application of 3DP technologies puts a new emphasis on the study of some of the process planning problems and issues that are related with the cost efficient use of 3DP systems and the quality of their products. As a result, the packing or platform layout optimization problem for the simultaneous fabrication of different parts has been identified as one of the most crucial tasks encountered in the process planning phase of 3DP. In the present paper a study of this problem that focuses on 3DP technologies that due to technical or quality reasons exclude the fabrication of a part on top of another, e.g. Stereolithography (SL) is presented. The methodologies discussed in the paper, employ a heuristic optimization technique (Simulated Annealing) in conjunction with two placement schemes, appropriately adapted to the problem.  The reliability of the methodologies under discussion is evaluated via a case study concerning representative “real-world” parts/objects with quite general free form geometry.


THREE METAHEURISTICS FOR THE CONSTRUCTION OF CONSTANT GC-CONTENT DNA CODES

R. Montemanni 1, D.H. Smith 2 and N. Koul 1

1 IDSIA - Università della Svizzera Italiana/SUPSI,

Via G. Buffi 13, 6904 Lugano, Canton Ticino, Switzerland

roberto@idsia.ch; nikhil.koul@usi.ch

2 Division of Mathematics and Statistics,

University of South Wales, Pontypridd, CF37 1DL, UK

derek.smith@southwales.ac.uk

Abstract. DNA codes are sets of words of fixed length n over the alphabet {A, C, G, T} which satisfy a number of combinatorial conditions. The combinatorial conditions considered are (i) minimum Hamming distance d, (ii) fixed GC-content and, in some cases (iii) minimum distance d between any codeword and the reverse Watson-Crick complement of any codeword. The problem is to find DNA codes with the maximum number of codewords. In this paper three different meta-heuristic approaches for the problem are discussed, and the outcome of an extensive experimental campaign, leading to many new best-known codes, is presented.


OPTIMIZING THE SUPPLY CHAIN CONFIGURATION WITH SUPPLY DISRUPTIONS

Ruiqing Xia and Hiroaki Matsukawa

Keio University, Yokohama, Japan

matsukawa@ae.keio.ac.jp

Abstract. The purpose of this paper is to investigate a supplier-retailer supply chain that experiences disruptions in supplier during the planning horizon. There might be multiple options to supply a raw material, to manufacture or assemble the product, and to transport the product to the customer.  While determine what suppliers, parts, processes, and transportation modes to select at each stage in the supply chain, options disruption must be considered. In this paper, we show that changes to the original plan induced by a disruption may impose considerable deviation costs throughout the system. When the production plan and the supply chain coordination scheme are designed in a static manner, as is most often the case, both will have to be adjusted under a disruption scenario. Using dynamic policies, we derive conditions under which the supply chain can be coordinated so that the maximum potential profit is realized.


A CLOSED-LOOP SUPPLY CHAIN REPACKAGING LINEAR OPTIMIZATION PROBLEM

José Díaz De La Hoz and Hiroaki Matsukawa

Keio University, Yokohama, Japan

jose.diaz.hoz@z8.keio.jp; matsukawa@ae.keio.ac.jp

Abstract. This paper presents a model for optimizing the costs of a complex production, distribution and package reprocessing industry. Building on previous work, closed-loop supply chain activities are incorporated in the form of a reverse flow of empty packages and reprocessing of those packages for further utilization. A linear programming mathematical framework is proposed for representing the different elements of the industry, allowing for high flexibility when applying the model to different industries. The optimization model provides the optimal decision variables for inventory management, production and recycling planning and scheduling, transport routing and empty package purchasing. The proposed framework allows for the introduction and alteration of multiple parameters in each of the different elements of the chain. Finally, a numerical example, involving a bottling industry that deals with standardized packaging, is solved utilizing Gurobi software, and a minimal cost solution is found, thus proving the model’s validity.


HEURISTIC SOLUTION METHODS FOR THE FIBER TO THE HOME CABLING PROBLEM

Matthieu Chardy 1 and Dorra Dhouib 2

1 Orange Labs, Issy-Les-Moulineaux, France

matthieu.chardy@orange.com

2 ENSTA Paristech, Palaiseau, France

Abstract. The deployment of Fiber To The Home (FTTH) technologies proves one of the most challenging issues for telecommunication operators. This paper focuses on the FTTH cabling problem which is modeled as a single-commodity flow problem with non-linear costs. Scalable heuristic approaches are presented and benchmarked on a real-life instances test set.


A FAST HEURISTIC FOR THE PRIZE-COLLECTING STEINER TREE PROBLEM

Murodzhon Akhmedov, Ivo Kwee and Roberto Montemanni

Dalle Molle Institute for Artificial Intelligence IDSIA-USI/SUPSI

Galleria 2, CH-6928 Manno, Switzerland

{murodzhon, roberto}@idsia.ch, ivo.kwee@ior.iosi.ch

Abstract. The Prize-Collecting Steiner Tree Problem (PCSTP) is a generalized version of the Steiner Tree Problem. PCSTP is well known and well studied problem in Combinatorial Optimization. Since PCSTP is NP-hard, it is computationally costly to achieve solutions for large instances. However, many real life network problems come with a wide range of variables and large instance sizes. Therefore, there is a need for efficient and fast heuristic algorithms to discover the hidden knowledge behind vast networks. There exists a fast heuristic algorithm for the Steiner Tree Problem in the literature, which is based on Minimum Spanning Trees. In this paper, we propose to extend the existing heuristic algorithm to solve PCSTP. The performance of the extended heuristic (MST-PCST) is evaluated on available benchmark instances from the literature. We also test MST-PCST on randomly generated huge graph instances with up to 40000 nodes and 120000 edges. We report the average gap percentage between the solutions of MST-PCST and existing solution approaches in the literature. Results show that overall performance of MST-PCST is promising with tolerable gap percentage and reasonable running time on larger instances. It has a significantly faster running time when graphs scale up which can shed light on large real world network instances.


GIS-BASED OPTIMIZATION FOR ADVANCED BIOFUELS SUPPLY CHAINS: A CASE STUDY IN TENNESSEE

T. Edward Yu, Lixia He, Burton C. English and James A. Larson

University of Tennessee, Knoxville, USA

{tyu1, llamber3, benglish, jlarson2}@utk.edu

Abstract. Biofuel production from lignocellulosic biomass (LCB) is being advocated as an alternative to fossil-based transportation fuels in the United States. Given the substantial technical barriers related to the harvest, storage, and transportation of the LCB feedstock, this study developed a GIS-based mixed integer programming model to evaluate how the spatial and geographic attributes affect the optimal placement and configuration of a switchgrass-based biofuel supply chain. Using west Tennessee as a case study, results indicate that the type of agricultural land converted to feedstock production and the transportation cost of hauling feedstock and biofuels were influential to the selection of the most profitable supply chain configuration.  The location of the conversion facilities and feedstock draw areas were also related to the choice of agricultural land use for feedstock production and the cost of hauling feedstock and advanced biofuels.


MULTI-NODE OFFER STACK OPTIMIZATION OVER ELECTRICITY NETWORKS

Anthony Downward, Danny Tsai and Yibo Weng

University of Auckland, Auckland, New Zealand

a.downward@auckland.ac.nz

Abstract. In this work we examine the problem that electricity generators face when offering power at multiple locations into an electricity market. The amount of power offered at each node can affect the price at the other node, so it is important to optimize all offers simultaneously. Even with perfect information (i.e. known demand, and known offers from competitors) this is a non-convex bi-level optimization problem. We first show how this can be formulated as an integer program using special ordered sets of type 2 (SOS2) enabling this problem to be solved efficiently. We then extend this work to allow for uncertainty, and hence find the profit maximising offer stacks at each node (as opposed to a single quantity, as in the deterministic case). We demonstrate the intuition that we can gain from this model in a simple two-node example, and discuss extensions to this work such as the co-optimization of reserve and generation, as well as demand-side bidding.


PRICE, QUALITY AND ADVERTISING DECISIONS CONSIDERING REFERENCE QUALITY EFFECTS: SEARCH VERSUS EXPERIENCE GOODS

Yanyan He 1, Qinglong Gou 1, Susan Li 2 and Zhimin Huang 2

1 School of Management, University of Science and Technology of China,

Hefei, Anhui, 230026, P.R. China

{heyanyan, tslg}@ustc.edu.cn

2 Robert B. Willumstad School of Business, Adelphi University,

Garden City, NY 11530-0701, USA

{li, huang}@adelphi.edu

Abstract. This research is stimulated from two facts. First, most products can be either search goods or experience goods. Consumers can learn the product quality of search goods before purchase, yet they can know that of experience goods until they have bought and used them for a certain period. Second, there is usually a kind of expectation on the quality of products, i.e. reference quality, formulated in a consumer's mind before he makes his purchase decision. Thus, when a consumer faces a search goods, he can compare its quality with his expectation and thus his decision will be influenced by the difference; yet he can make his decision just depending on his expectation when he occurs to an experience one since he cannot observe its quality before purchase. In this paper, we incorporate this fact with a modified Nerlove–Arrow model and then investigate firms' joint decisions on price, quality and advertising. The firms' optimal decisions are derived out under a differential game theory framework. Our results show that when the firms make their decisions mentioned above, they should consider the characteristics of their products seriously.


A DYNAMIC PORTFOLIO SELECTION MODEL USING A NONSTATIONARY INVESTMENT TARGET ACCORDING TO THE STOCK MARKET FORECAST

Jongbin Jung and Seongmoon Kim

School of Business, Yonsei University, Seoul, South Korea

kimsm@yonsei.ac.kr

Abstract. In this paper, we propose an adaptive investment strategy (AIS) based on a dynamic portfolio selection model (DPSM) that uses a time-varying investment target according to the market forecast. The DPSM allows for flexible investments, setting relatively aggressive investment targets when market growth is expected and relatively conservative targets when the market is expected to be less attractive. By dynamically determining the investment target, the DPSM allows construction of portfolios that are more responsive to market changes. When the proposed DPSM is implemented in real-life investment scenarios using the AIS, the portfolio is rebalanced according to a predefined rebalancing cycle and the model’s input parameters are estimated on each rebalancing date using an exponentially weighted moving average (EWMA) estimator. To evaluate the performance of the proposed approach, a 7-year investment experiment was conducted using historical stock returns data from 10 different stock markets around the world. Performance was assessed and compared using diverse measures. Superior performance was achieved using the AIS proposed herein compared to various benchmark approaches for all performance measures.


SIMHEURISTICS AND BIASED RANDOMIZATION OF HEURISTICS TO SOLVE COMBINATORIAL OPTIMIZATION PROBLEMS IN LOGISTICS AND TRANSPORTATION

Javier Faulin 1 and Angel Juan 2

1 Department of Statistics and Operations Research, Public University of Navarre, Pamplona, Spain

javier.faulin@unavarra.es

2 Department of Computer Science, Open University of Catalonia, Barcelona, Spain

Abstract. Combinatorial optimization problems are a very common research area in the Logistics and Transportation field and have been analyzed and solved using different types of procedures and algorithms. Here, we introduce two new interconnected methodologies called Biased Randomization and Simheuristics. The Biased Randomization of a heuristic is a way to try to escape from the local optima in a combinatorial optimization problem using biased probability distributions to generate a set of potential good solutions, not necessarily optimal, to a deterministic problem. When we consider stochastic problems and we use simulation techniques to produce a big number of potential good solutions, a Simheuristics method is being employed. Both kinds of methods can be applied to solve an assorted group of problems such as the capacitated vehicle routing problem, the vehicle routing problem with stochastic demands, the capacitated arc routing problem, permutation flowshop sequencing problem, or the electric vehicle routing problem, among others. The results obtained using these procedures are very competitive from the computational point of view and very practical in the generations of good solutions for real world cases.


OPTIMIZE SCHEDULING AND ROUTING AT AN AIRPORT

Tomas Eric Nordlander, Patrick Schittekat, Dag Kjenstad, Carlo Mannino and Morten Smedsrud

SINTEF ICT, Oslo, Norway

{tomas.nordlander, patrick.schittekat, dag.kjenstad, carlo.mannino, morten.smedsrud}@sintef.no 

Abstract. Air Traffic Management focus to provide efficient and safe movement of airplanes at and near the airports. This is a very complex problem that is normally divided into Arrival, Surface and a Departure Management Problem. While this division of responsibility may be practical for managing the complexity it does prevent the high level of coordination needed to ensure that global optimal decisions are made by each controller. The effect of one controller's decision propagates through to other controllers. E.g. one small valuable adjustment of one controller can very well create havoc for other controllers further down the trajectory. We present an integrated approach to the overall problem along with an optimization algorithm that heuristically decomposes the problem so routing, sequencing, and conflicts resolution are carried out in subsequent stages. Our approach has been validated in experiments on Hamburg airport which showed remarkable improvements in punctuality and taxi times compared to the expert controllers. 


© ORLab Analytics Inc