ICORES 2016 Abstracts


Area 1 - Methodologies and Technologies

Full Papers
Paper Nr: 2
Title:

A Comparative Analysis of Pickup Forecasting Methods for Customer Arrivals in Airport Carparks

Authors:

Andreas Papayiannis, Paul Johnson and Peter Duck

Abstract: Accurate forecasts of customer demand lie at the core of any successful revenue management system. Most research has focused upon studying such methods for the airline and hotel industry. In this paper, we present a comparative analysis of various forecasting methods which we apply to the rapidly evolving airport carparking (ACP) industry. We use real ACP booking data from four distinct carparks of a major airport in UK to forecast customer arrivals for one to eight weeks out in the future. Conclusions are reached with regards to which forecasting methods perform best in this operating environment, and whether there is any benefit in employing complex methods over simpler ones.

Paper Nr: 13
Title:

A Variable Neighbourhood Search Algorithm with Compound Neighbourhoods for VRPTW

Authors:

Binhui Chen, Rong Qu, Ruibin Bai and Hisao Ishibuchi

Abstract: The Vehicle Routing Problem with Time Windows (VRPTW) consists of constructing least cost routes from a depot to a set of geographically scattered service points and back to the depot, satisfying service time interval and capacity constraints. A Variable Neighbourhood Search algorithm with Compound Neighbourhoods is proposed to solve VRPTW in this paper. A number of independent neighbourhood operators are composed into compound neighbourhood operators in a new way, to explore wider search area concerning two objectives (to minimize the number of vehicles and the total travel distance) simultaneously. Promising results are obtained on benchmark datasets.

Paper Nr: 20
Title:

A Cuckoo Search Clustering Algorithm for Design Structure Matrix

Authors:

Hayam G. Wahdan, Sally S. Kassem and Hisham M. Abdelsalam

Abstract: Modularity is a concept that is applied to manage complex systems by breaking them down into a set of modules that are interdependent within and independent across the modules. Benefits of modularity are often achieved from module independence that allows for independent development to reduce overall lead time and to reach economies of scale due to sharing similar modules across products in a product family. The main objective of this paper is to support design products under modularity, cluster products into a set of modules or clusters, with maximum internal relationships within a given module and minimum external relationships with other modules. The product to be designed is represented in the form of a Design Structure Matrix (DSM) that contains a list of all product components and the corresponding information exchange and dependency patterns among these components. In this research Cuckoo Search (CS) optimization algorithm is used to find the optimal number of clusters and the optimal assignment of each component to specific cluster in order to minimize the total coordination cost. Results obtained showed an improved performance compared to published studies.

Paper Nr: 24
Title:

Sequential Games with Finite Horizon and Turn Selection Process - Finite Strategy Sets Case

Authors:

Rubén Becerril-Borja and Raúl Montes-de-Oca

Abstract: A class of models of sequential games is proposed where the turns of decision are random for all players. The models presented show different variations in this class of games. In spite of the random nature of the turn selection process, first the number of turns per player is fixed, and afterwards models without this property are considered, as well as some that allow changes in other components. For all the models, a series of results are obtained to guarantee the existence of Nash equilibria. A possible application is shown for drafting athletes in sports leagues.

Paper Nr: 32
Title:

A Multi-period Vertex Cover Problem and Application to Fuel Management

Authors:

Marc Demange and Cerasela Tanasescu

Abstract: We consider a generalisation of MIN WEIGHTED VERTEX COVER motivated by a problem in wildfire prevention. The problem is defined for a fixed number of time periods and we have to choose, at each period, some vertices to be deleted such that we never have two adjacent remaining vertices. The specificity is that whenever a vertex is deleted it reappears after a given number of periods. Consequently we may need to delete a single vertex several times. The objective is to minimise the total weight (cost) of deleted vertices. The considered application motivates the case of planar graphs. While similar problems have been mainly solved using mixed integer linear models (MIP) we investigate a graph approach that allows to take into account the structure of the underlying graph. We use a reduction to the usual MIN WEIGHTED VERTEX COVER to devise efficient approximation algorithms and to raise some polynomial classes.

Paper Nr: 58
Title:

A Complementarity Problem Formulation for Chance-constraine Games

Authors:

Vikas Vikram Singh, Oualid Jouini and Abdel Lisser

Abstract: We consider a two player bimatrix game where the entries of each player’s payoff matrix are independent random variables following a certain distribution. We formulate this as a chance-constrained game by considering that the payoff of each player is defined by using a chance-constraint. We consider the case of normal and Cauchy distributions. We show that a Nash equilibrium of the chance-constrained game corresponding to normal distribution can be obtained by solving an equivalent nonlinear complementarity problem. Further if the entries of the payoff matrices are also identically distributed with non-negative mean, we show that a strategy pair, where each player’s strategy is the uniform distribution on his action set, is a Nash equilibrium of the chance-constrained game. We show that a Nash equilibrium of the chance-constrained game corresponding to Cauchy distribution can be obtained by solving an equivalent linear complementarity problem.

Short Papers
Paper Nr: 5
Title:

Transport Planning in Processing Plants for the Fruit Industry

Authors:

Wladimir E. Soto-Silva, Marcela C. González-Araya, Lluis M. Pla-Aragones and Esteve Nadal-Roig

Abstract: Processing plants are central for the operation of fruit supply chains. One of the main aspects to consider is fruit transportation to the processing plant. Hence, this work proposes a mixed integer linear programming model to support the fruit transport planning from the storage facilities to the processing plant. The aim of the model is to minimize the daily transportation costs and associated costs of different storage facilities from where fruits are supplied to the plant in order to meet the demand. The model considers plant processing capacity, fruit demand, number and type of trucks available and the inventory of fruit in each type of storage facilities. The model was applied to a real case study of a processing plant located in the O'Higgins Region (Chile), where reported savings only in transport costs reached about 23 percent.

Paper Nr: 28
Title:

Fixed-sequence Single Machine Scheduling and Outbound Delivery Problems

Authors:

Azeddine Cheref, Alessandro Agnetis, Christian Artigues and Jean-Charles Billaut 

Abstract: In this paper, we study an integrated production an outbound delivery scheduling problem with a predefined sequence. The manufacturer has to process a set of jobs on a single machine and deliver them in batches to multiple customers. A single vehicle with limited capacity is used for the delivery. Each job has a processing time and a specific customer location. Starting from the manufacturer location, the vehicle delivers a set of jobs which constitute a batch by taking into account the transportation times. Since the production sequence and delivery sequence are fixed and identical, the problem consists in deciding the composition of batches. We prove that for any regular sum-type objective function of the delivery times, the problem in NP-hard in the ordinary sense and can be solved in pseudopolynomial time. A dynamic programming algorithm is proposed.

Paper Nr: 41
Title:

An Interbank Market Network Model based on Bank Credit Lending Preference

Authors:

Tao Xu, Jianmin He and Shouwei Li

Abstract: An interbank market network model based on bank credit lending preference is built in this paper to explain the formation mechanism of interbank market network structure. As well, we analyze the impact of credit lending risk preference on network topology structure, which includes degree distribution, network clustering coefficient, average shortest path length and network efficiency. Simulation results demonstrate that the accumulation degree follows dual power law distribution with credit lending risk preference parameter value equal or greater than 1, while the accumulation degree follows power law distribution with credit lending risk preference parameter value smaller than 1. The interbank market network shows small world topology property. With the increasing of bank credit lending risk preference, the average shortest path length decreases but network efficiency improves, which enhances the stability of the network.

Paper Nr: 44
Title:

A Two-stage Stochastic Programming Approach for the Traveling Salesman Problem

Authors:

Pablo Adasme, Rafael Andrade, Janny Leung and Abdel Lisser

Abstract: In the context of combinatorial optimization, recently some efforts have been made by extending classical optimization problems under the two-stage stochastic programming framework. In this paper, we introduce the two-stage stochastic traveling salesman problem (STSP). Let G = (V,ED ∪ES) be a non directed complete graph with set of nodes V and set of weighted edges ED ∪ES where ED ∩ES = 0/. The edges in ED and ES have deterministic and uncertain weights, respectively. Let K = {1,2,··· ,|K|} be a given set of scenarios referred to the uncertain weights of the edges in ES. The STSP consists in determining Hamiltonian cycles of G, one for each scenario s ∈ K, sharing the same deterministic edges while minimizing the sum of the deterministic weights plus the expected weight over all scenarios associated with the uncertain edges. We propose two compact models and a formulation with an exponential number of constraints which are adapted from the classic TSP. One of the compact models allows to solve instances with up to 40 nodes and 5 scenarios to optimality. Finally, we propose an iterative procedure that allows to compute optimal solutions and tight lower bounds within very small CPU time.

Paper Nr: 52
Title:

Incorporating Explanatory Effects of Neighbour Airports in Forecasting Models for Airline Passenger Volumes

Authors:

Nilgun Ferhatosmanoglu and Betul Macit

Abstract: Forecasting airline passenger volumes can be helpful for flight and airport capacity planning. While there are many parameters affecting the passenger volume, to our knowledge no work has directly studied the effect of neighbour airports in modelling of passenger volumes. We develop an integrated model for forecasting the number of passengers arriving/departing an airport, considering the airport’s interactions with its neighbour airports. In particular, we analyse the time series of the flights arriving to and departing from two largest airports in Turkey, namely Ankara Esenboga and Istanbul Ataturk Airports, and explore the interactions between these airports by using them as regressors for each other. We also apply independent models based on TBATS which was previously proposed in the literature to handle multiple seasonalities. In our experiments, TBATS performs better than ARIMA for independent modelling, and TBATS with multiple seasonal periods outperforms TBATS with single seasonality in majority of the cases. In several cases, the forecasting accuracy increases when the neighbour airports’ traffic data is used in modeling the passenger volumes.

Paper Nr: 54
Title:

Distributionally Robust Games with Risk-averse Players

Authors:

Nicolas Loizou

Abstract: We present a new model of incomplete information games without private information in which the players use a distributionally robust optimization approach to cope with the payoff uncertainty. With some specific restrictions, we show that our “Distributionally Robust Game” constitutes a true generalization of three popular finite games. These are the Complete Information Games, Bayesian Games and Robust Games. Subsequently, we prove that the set of equilibria of an arbitrary distributionally robust game with specified ambiguity set can be computed as the component-wise projection of the solution set of a multi-linear system of equations and inequalities. For special cases of such games we show equivalence to complete information finite games (Nash Games) with the same number of players and same action spaces. Thus, when our game falls within these special cases one can simply solve the corresponding Nash Game. Finally, we demonstrate the applicability of our new model of games and highlight its importance.

Paper Nr: 59
Title:

An Efficient Label-setting Algorithm for the Bi-objective Shortest Path Problem

Authors:

Antoine Giret, Yannick Kergosien, Gael Sauvanet and Emmanuel Neron

Abstract: In this paper, we consider a classical Bi-objective Shortest Path problem (BSP) that takes into account both distance and insecurity criteria. This work is in collaboration with an enterprise who provide a web platform called G´eov´elo that aims to propose routes for cycling. We propose a new exact method to solve a BSP, called Label Setting algorithm with Dynamic update of Pareto Front (LSDPF), which aims to find all non-dominated solutions of the problem. Different exploration strategies have been proposed and tested. Numerical experiments on real data sets and on instances of the literature were conducted. Comparison with recent benchmarks algorithms solving BSP - the bounded Label Setting algorithm by (Raith, 2010) and the pulse algorithm by (Duque et al., 2015) - shows that our method outperform these benchmarks algorithms.

Paper Nr: 74
Title:

Urban Crime Mitigation - A Model to Derive Criminal Patterns and Determine Defender Placement to Reduce Opportunistic Crime

Authors:

Solomon Y. Sonya, Luke Brantley and Meagan Whitaker

Abstract: Urban opportunistic crime is a problem throughout the world causing financial, physical, and emotional damages to innocent citizens and organizations. Opportunistic crimes require minimal reconnaissance and preparation in order to conduct an attack (e.g., burglary, robbery, vandalism, and assault). Opportunistic criminals are more spontaneous in nature making their actions difficult to anticipate and create an approach to reduce these crimes. Statistical analysis of crimes may reveal distinct patterns from which a strategy can be created to better mitigate future crimes. This paper describes analysis performed on real-world campus crime data in which distinct correlations were discovered to determine the significant factors that motivate opportunistic crime. This research concludes by developing a dynamic defender placement strategy that adapts over time to reduce the utility of opportunistic crimes. The research contribution allows for the determination of significant factors motivating opportunistic crime and releases a program that maps crime occurrences over time, determines the minimum defender allocation for a given area, and dynamically specifies defender placement strategy to mitigate future crime. The novelty of this approach allows for application to other campuses, shopping complexes, and living districts to form conclusions about opportunistic criminal activity and formulate an approach to abate such crimes.

Posters
Paper Nr: 6
Title:

Double Ant Colony System to Improve Accessibility after a Disaster

Authors:

Víctor Sacristán, Antonio Jiménez-Martín and Alfonso Mateos

Abstract: We propose a novel double ant colony system to deal with accessibility issues after a natural or man-made disaster. The aim is to maximize the number of survivors that reach the nearest regional center (center of economic and social activity in the region) in a minimum time by planning which rural roads damaged by the disaster should be repaired given the available financial and human resources. The proposed algorithm is illustrated by means of a large instance based on the Haiti natural disasters in August-September 2008.

Paper Nr: 7
Title:

An Industry-focused Advertising Model

Authors:

A. Murray

Abstract: In this paper a model is created that may be effectively used to determine the optimal spending trajectory for an advertising campaign. Given a sufficient data set, all parameters present in the model should be easily determinable, or at least accurately approximated, and justifications are given for the form of all parts of the model. Finally, the solution to both the deterministic and stochastic versions of the model are given.

Paper Nr: 9
Title:

Multi-Objective Vehicle Routing Problem with Time Windows and Fuel Consumption Minimizing

Authors:

Seyed Farid Ghannadpour and Mohsen Hooshfar

Abstract: Transportation often represents the most important single element in logistics costs and its reduction and finding the best routes that a vehicle should follow through a network is an important decision. the energy cost is a significant part of total transportation cost and it is important to improve the operational efficiency by decreasing energy consumption. Unlike most of the studies trying to minimize the cost by minimizing overall travelling distance, the energy minimizing which meets the latest requirements of green logistics, is considered in this paper. the customers' priority for servicing is considered as well. Besides, the model is interpreted as multi-objective optimization where, the energy consumed and the total fleet are minimized and the total satisfaction rates of customers is maximized. A new solution based on the evolutionary algorithm is proposed and its performance is compared with the CPLEX Solver. Results illustrate the efficiency and effectiveness of proposed approach.

Paper Nr: 11
Title:

Sheduling Mobil Medical Units for Home-healthcare Service

Authors:

Ciro Alberto Amaya and John Espitia

Abstract: This paper addresses a shift-scheduling and localization problem of medical staff for home-healthcare services. In this problem a private company has to decide where to locate its mobile units and its operational times. Locations and schedules define the system capacity to attend patients, capacity produces acceptable service level but operational costs, in contrast, a capacity overestimation requires subcontracting services and consequently a decrease in expected profit. In this talk we present the situation studied and a mathematical approach to deal with. The method was used in a real situation improving net profit and increased the expected served demand.

Paper Nr: 12
Title:

Single and Multiple Objective Optimization Models for Opportunistic Preventive Maintenance

Authors:

Carlos Henggeler Antunes, Maria João Alves, Joana Dias, Teresa Gomes, Benjamim Cardoso and José Freitas

Abstract: This paper presents single and multiple objective deterministic optimization models for opportunistic preventive maintenance of multi-component systems. The single objective model develops an aggregate cost objective function encompassing costs of replacement, fixed costs associated with maintenance interventions and costs of component dismounting whenever the replacement of a given component implies disassembling others. Two multiple objective models are proposed, which enable to explore the trade-offs between minimizing costs vs. the number of maintenance interventions and minimizing costs vs. maximizing the remaining lifetime of components at the end of the planning period. Constraints refer to the requirement of replacing each component before the end of its lifetime and consistency restrictions to allow opportunistic maintenance and dismounting requirements.

Paper Nr: 14
Title:

On Duality with Support Functions for a Multiobjective Fractional Programming Problem

Authors:

Indira P. Debnath and S. K. Gupta

Abstract: In this article, a different class of function called (K × Q)-F-type I has been introduced. Further, we have formulated a problem over cones and appropriate duality results have been established taking the concerned functions to be (K ×Q)- F-type I. The results which we have put forward in the paper generalizes some of the known results appeared in the literature.

Paper Nr: 16
Title:

ACO and CP Working Together to Build a Flexible Tool for the VRP

Authors:

Negar ZakeriNejad, Daniel Riera and Daniel Guimarans

Abstract: In this paper a flexible hybrid methodology, combining Ant Colony Optimisation (ACO) and Constraint Programming (CP), is presented for solving Vehicle Routing Problems (VRP). The stress of this methodology is on the word ‘flexible’: It gives reasonably good results to changing problems without high solution redesign efforts. Thus a different problem with a new set of constraints and objectives requires no changes to the search algorithm. The search part (driven by ACO) and the model of the problem (included in the CP part) are separated to take advantage of their best attributes. This separation makes the application of the framework to different problems much simpler. To assess the feasibility of our approach, we have used it to solve different instances of the VRP family. These instances are built by combining different sets of constraints. The results obtained are promising but show that the methodology needs deeper communication between ACO and CP to improve its performance.

Paper Nr: 22
Title:

A Binary Cuckoo Search Algorithm for Solving Project Portfolio Problem with Synergy Considerations

Authors:

Mohammed M. S. El-Kholany and Hisham M. Abdelsalam

Abstract: Many companies are moving toward a project-oriented way of managing their businesses while considering the risk of losing the limited available resources because of selecting incorrect projects to be executed. With a number of candidate projects larger than those which can be funded, organizations aim to select projects that maximize benefit and enhance their competitive advantages. These reasons force organizations to search for more effective techniques to improve their decision with project selection. The consideration of synergy between projects is not addressed much in literature. This paper proposes new meta-heuristic technique which is Cuckoo Search Algorithm to solve Project Portfolio Selection problem with synergy among various projects is considered. Four scenarios are experimented on 0 – 1 optimization problem contains two constraints budget and segmentation to show performance algorithm through iterations with changing scenarios in addition to the effect of synergy on projects selection and total benefit for the organization.

Paper Nr: 25
Title:

Graph Fragmentation Problem

Authors:

Juan Piccini, Franco Robledo and Pablo Romero

Abstract: A combinatorial optimization problem called Graph Fragmentation Problem (GFP) is introduced. The decision variable is a set of protected nodes, which are deleted from the graph. An attacker picks a non-protected node uniformly at random from the resulting subgraph, and it completely affects the corresponding connected component. The goal is to minimize the expected number of affected nodes S. The GFP finds applications in fire fighting, epidemiology and robust network design among others. A Greedy notion for the GFP is presented. Then, we develop a GRASP heuristic enriched with a Path-Relinking post-optimization phase. Both heuristics are compared on the lights of graphs inspired by a real-world application.

Paper Nr: 35
Title:

Mixed Integer Program Heuristic for Linear Ordering Problem

Authors:

Ehsan Iranmanesh and Ramesh Krishnamurti

Abstract: The Linear Ordering Problem is a classic optimization problem which can be used to model problems in graph theory, machine scheduling, and voting theory, many of which have practical applications. Relatively recently, there has been some success in using Mixed Integer Program (MIP) heuristic for NP-hard optimization problems. We report our experience with using a MIP heuristic for the problem. Our heuristic generates a starting feasible solution based on the Linear Programming solution to the IP formulation for the Linear Ordering Problem. For each starting solution, a neighborhood is defined, again based on the LP solution to the problem. A MIP solver is then used to obtain the optimal solution among all the solutions in the neighborhood. The MIP heuristic shows promise for large problems of hard instances.

Paper Nr: 49
Title:

Approaching a Target using a Protection Feature based on Received Signal Strength Indicator

Authors:

Kazuyuki Ishii and Naoshi Sato

Abstract: The received signal strength indicator (RSSI) which can be obtained during wireless communication, depending on communication distance, and is used to estimate the distance between a sender and receiver. We focus on the RSSI to determine whether a mobile node is approaching or departing from a target node (T N). To determine approach or departure, we implement the protection step number (PSN) as a protection feature that determines approach or departure when RSSI varies N times of the PSN in a row. N is designed according to RSSI deviation, and the value is computed statistically. In this paper, we demonstrate a method for approaching a TN based on RSSI with and without the proposed PSN.

Paper Nr: 66
Title:

Numerical Experiments with a Primal-Dual Algorithm for Solving Quadratic Problems

Authors:

Derkaoui Orkia and Lehireche Ahmed

Abstract: This paper provides a new variant of primal-dual interior-point method for solving a SemiDefinite Program (SDP). We use the PDIPA (primal-dual interior-point algorithm) solver entitled SDPA (SemiDefinite Programming Algorithm). This last uses a classical Newton descent method to compute the predictor-corrector search direction. The difficulty is in the computation of this line-search, it induces high computational costs. Here, instead we adopt a new procedure to implement another way to determine the step-size along the direction which is more efficient than classical line searches. This procedure consists in the computation of the step size in order to give a significant decrease along the descent line direction with a minimum cost. With this procedure we obtain à new variant of SDPA. The comparison of the results obtained with the classic SDPA and our new variant is promising.

Paper Nr: 71
Title:

Selective Maintenance for Failure-prone Multi-state Systems When the Durations of Missions and Scheduled Breaks Are Stochastic

Authors:

A. Khatab and E. H. Aghezzaf

Abstract: This paper addresses the selective maintenance optimization problem for a multi-component and multi-state system (MSS). The system performs several missions with breaks between each two consecutive missions. At the end of a mission, the reliability of the system is defined as the probability that the system satisfies the required demand level during the next mission. This probability is evaluated using the z-transform method. To improve the system’s reliability, its components are maintained during breaks. To each component, a list of maintenance actions is available from minimal repair to overhaul through imperfect maintenance actions. Durations of missions and breaks are considered not constant but rather stochastic. These durations are therefore modeled as random variables with appropriate probability distributions. The selective maintenance optimization problem proposed is modeled as a non-linear and stochastic program. The fundamental constructs and the relevant parameters of this decision-making problem are solely investigated and discussed. An illustrative example is provided to demonstrate the added value of solving this selective maintenance problem as a stochastic optimization program.

Area 2 - Applications

Full Papers
Paper Nr: 19
Title:

Fence Patrolling with Two-speed Robots

Authors:

Jurek Czyzowicz, Konstantinos Georgiou, Evangelos Kranakis, Fraser MacQuarrie and Dominik Pajak

Abstract: A fence is to be patrolled collectively by n robots. At any moment a robot may move in one of the two possible states: walking or patrolling. Each state is associated with a maximal moving speed which cannot be exceeded. We want to schedule the perpetual movements of the robots so as to minimize the idleness, defined as the smallest time interval within which every point is always visited by some robot. First, we give a centralized algorithm constructing schedules with optimal idleness, and subsequently we show an interesting application to a transportation problem concerning Scheduling with Regular Delivery. Our main contribution is the study of distributed, dynamical schedules for patrolling robots with only primitive capabilities. Surprisingly, we are able to design a dynamic schedule for very weak collections of two robots (silent, oblivious, passively mobile), achieving the optimal idleness. Part of our contribution is a very technical analysis of the dynamics of special families of dynamical systems of n robots that we call regular. For such systems we also propose a highly non-trivial O(n2) algorithm to decide whether or not robots converge to a stable configuration thus verifying if the dynamic schedule is optimal.

Paper Nr: 26
Title:

A Mass-flow based MILP Formulation for the Inventory Routing with Explicit Energy Consumption

Authors:

Yun He, Cyril Briand and Nicolas Jozefowiez

Abstract: In this paper, we present a new mass-flow based Mixed Integer Linear Programming (MILP) formulation for the Inventory Routing Problem (IRP) with explicit energy consumption. The problem is based on a multi-period single-vehicle IRP with one depot and several customers. Instead of minimizing the distance or inventory cost, the problem takes energy minimization as an objective. In this formulation, flow variables describing the transported mass serve as a link between the inventory control and the energy estimation. Based on physical laws of motion, a new energy estimation model is proposed using parameters like vehicle speed, average acceleration rate and number of stops. The solution process contains two phases with different objectives: one with inventory and transportation cost minimization as in traditional IRP, the other with energy minimization. Using benchmark instances for inventory routing with parameters for energy estimation, experiments have been conducted. Finally, the results of these two solution phases are compared to analyse the influence of energy consumption to the inventory routing systems.

Paper Nr: 27
Title:

Mean Response-Time Minimization of a Soft-Cascade Detector

Authors:

Francisco Rodolfo Barbosa-Anda, Cyril Briand, Frédéric Lerasle and Alhayat Ali Mekonnen

Abstract: In this paper, the problem of minimizing the mean response-time of a soft-cascade detector is addressed. A soft-cascade detector is a machine learning tool used in applications that need to recognize the presence of certain types of object instances in images. Classical soft-cascade learning methods select the weak classifiers that compose the cascade, as well as the classification thresholds applied at each cascade level, so that a desired detection performance is reached. They usually do not take into account its mean response-time, which is also of importance in time-constrained applications. To overcome that, we consider the threshold selection problem aiming to minimize the computation time needed to detect a target object in an image (i.e., by classifying a set of samples). We prove the NP-hardness of the problem and propose a mathematical model that takes benefit from several dominance properties, which are put into evidence. On the basis of computational experiments, we show that we can provide a faster cascade detector, while maintaining the same detection performances.

Paper Nr: 29
Title:

Police Officer Dynamic Positioning for Incident Response and Community Presence - Using Maximum Demand Coverage and Kernel Density Estimation to Plan Patrols

Authors:

Johanna Leigh, Lisa Jackson and Sarah Dunnett

Abstract: Police Forces are under a constant struggle to provide the best service possible with limited and decreasing resources. One area where service cannot be compromised is incident response. Resources which are assigned to incident response must provide attendance to the scene of an incident in a timely manner to protect the public. To ensure the possible demand is met maximum coverage location planning can be used so response officers are located in the most effective position for incident response. This is not the only concern of response officer positioning. Location planning must also consider targeting high crime areas, hotspots, as an officer presence in these areas can reduce crime levels and hence reduce future demand on the response officers. In this work hotspots are found using quadratic kernel density estimation with historical crime data. These are then used to produce optimal dynamic patrol routes for response officers to follow. Dynamic patrol routes result in reduced response times and reduced crime levels in hotspot areas resulting in a lower demand on response officers.

Paper Nr: 31
Title:

Delineation of Rectangular Management Zones Under Uncertainty Conditions

Authors:

Jose L. Saez and Victor M. Albornoz

Abstract: In this article we cover the problem of generating a partition of an agricultural field into rectangular and homogeneous management zones or quarters according to a given soil property, which has variability in time that is presented as a number of possible scenarios. This problem combines aspects of precision agriculture and optimization with the purpose of achieving a site and time specific management of the field properties that is consistent and effective in time for a medium term horizon. More specifically, we propose a two stage integer stochastic linear programming model with recource that solves the problem of generating a partition facing a finite number of future scenarios, with a solution that gives satisfactory results to any possible value of the chosen soil property. We describe the proposed model, the adopted methodology and the results achieved with this methodology.

Paper Nr: 42
Title:

A Risk-based Real Options Framework for Flexible Technology Planning

Authors:

Juite Wang, Chuan-Hung Cheng, Yung-I Lin and Chih-Hsin Chang

Abstract: Although the importance of R&D is well understood by technology-based firms, with the increasing uncertainty in technology development and market trends in recent years, managing uncertain R&D projects to enhance competitive technological position is still a major challenge for those firms. This research develops a technology planning framework that integrates R&D risk management with real options analysis enables technology-based firms to allocate their limited R&D resources with managerial flexibility for maximizing the expected market value of R&D project under uncertainty. The proposed technology planning framework consists of four stages: technology roadmapping, risk identification, risk response planning, and flexible plan optimization. Since technology development usually involves great uncertainty at early R&D stages, the Monte-Carlo simulation optimization technique is applied to evaluate and select optimal technology plans under different scenarios. The developed methodology is illustrated with a case study of ASIC power module technology development project in Taiwan.

Paper Nr: 46
Title:

The Effect of Cooperation in Pickup and Multiple Delivery Problems

Authors:

Philip Mourdjis, Fiona Polack, Peter Cowling, Yujie Chen and Martin Robinson

Abstract: Small logistics companies operate in many towns and cities across the UK, and need to be able to compete with larger delivery companies who can leverage economies of scale to provide lower costs to customers. If small companies were willing to work together, all could benefit from reduced operating costs, enabling them to compete and survive against larger delivery companies. In cooperation with Transfaction Ltd., we investigate dynamic scheduling of shared loads for real-world, long distance truck haulage in the UK. We model the problem as a dynamic pickup and multiple delivery problem (PMDP). The PMDP is a one-many problem (one pickup, many drop-offs), unlike the more widely researched one-one (pickup and delivery problem, PDP) and one-many-one (vehicle routing problem, VRP) problems.

Paper Nr: 47
Title:

Risk Driven Analysis of Maintenance for a Large-scale Drainage System

Authors:

Yujie Chen, Fiona Polack, Peter Cowling, Philip Mourdjis and Stephen Remde

Abstract: Gully pots or storm drains are located at the side of roads to provide drainage for surface water. We consider gully pot maintenance as a risk-driven maintenance problem. Our simulation considers the risk impact of gully pot failure and its failure behaviour. In this paper, we focus on two factors, the issue of parked cars and up-to-date gully pots status information, that may affect the scheduling of maintenance actions. The aim is to discover potential investment directions and management policies that will improve the efficiency of maintenance. We find that the “untimely system status information” is a dominant factor that weakens the current maintenance. Low-cost sensor technique could be a good development.

Paper Nr: 48
Title:

Efficient Large-scale Road Inspection Routing

Authors:

Yujie Chen, Peter Cowling, Stephen Remde and Fiona Polack

Abstract: Gaist Solutions Ltd. carries out large scale surveys for UK road inspection. To estimate the total distance that vehicles travel, we model routing as a Chinese Postman Problem. We propose a novel graph reduction approach that dramatically speeds up the calculation of the Chinese Postman Tour for large-scale road networks. Because the analysis of large road-network graphs is now possible, planners can explore the effects of changes to traditional inspection techniques and scheduling. Case studies of road networks from six UK cities and the county of Norfolk are tested. The graph reduction process is also analysed on ten randomly generated road networks with different characteristics, to show its ability and give advice for suitable use.

Paper Nr: 50
Title:

A Discrete Event Simulation Approach for Quantifying Risks in Manufacturing Processes

Authors:

Renaud De Landtsheer, Gustavo Ospina, Philippe Massonet, Christophe Ponsard, Stephan Printz, Lasse Härtel and Johann Philipp von Cube

Abstract: Nowadays supply chains have to face an increasing number of risks related to the globalisation, especially impacting the procurement processes. Even though tools are available to help companies in addressing those risks, most companies, even larger ones, still have problems to adequately quantify the risks and assess to what extend an alternative could address them. The aim of our work is to provide companies with a software supported methodology to quantify such risks and elaborate adequate risk mitigation strategies at an optimal cost. Based on a survey conducted about the risk management practices and needs within companies, we developed a tool that enables a constant focus on risks by enabling the easy expression of key risks together with the process model and hence help to focus the granularity of the model at the right level. A model-based simulator can then efficiently evaluate these risks thanks to well-known Monte-Carlo simulation techniques. Our main technical contribution lies in the development of an efficient discrete event simulation (DES) engine together with a query language which can be used to measure business risks based on simulation results. We demonstrate the expressiveness and performance of our approach by benchmarking it on a set of cases originating from the industry and covering a large set of risk categories.

Paper Nr: 51
Title:

A Stochastic Version of the Ramsey’s Growth Model

Authors:

Gabriel Zacarías-Espinoza, Hugo Cruz-Suárez and Enrique Lemus-Rodríguez

Abstract: In this paper we study a version of Ramsey’s discrete time Growth Model where the evolution of Labor through time is stochastic. Taking advantage of recent theoretical results in the field of Markov Decision Processes, a first set of conditions on the model are established that guarantee a long-term stable behavior of the underlying Markov chain.

Paper Nr: 61
Title:

Mixed Integer Programming with Decomposition for Workforce Scheduling and Routing with Time-dependent Activities Constraints

Authors:

Wasakorn Laesanklang, Dario Landa-Silva and J. Arturo Castillo-Salazar

Abstract: We present a mixed integer programming decomposition approach to tackle workforce scheduling and routing problems (WSRP) that involve time-dependent activities constraints. The proposed method is called repeated decomposition with conflict repair (RDCR) and it consists of repeatedly applying a phase of problem decomposition and sub-problem solving, followed by a phase dedicated to conflict repair. Five types of time-dependent activities constraints are considered: overlapping, synchronisation, minimum difference, maximum difference, and minimum-maximum difference. Experiments are conducted to compare the proposed method to a tailored greedy heuristic. Results show that the proposed RDCR is an effective approach to harness the power of mixed integer programming solvers to tackle the difficult and highly constrained WSRP in practical computational time.

Short Papers
Paper Nr: 30
Title:

Blood Products Inventory Pickup and Delivery Problem under Time Windows Constraints

Authors:

Imane Hssini, Nadine Meskens and Fouad Riane

Abstract: The inventory pickup and delivery problem with time windows (IPDPTW) addressed in this paper is a variant of the well known inventory routing problem (IRP). It consists in combining the inventory management problem and the problem of delivery and collection under the constraints of time window. In our study, we apply this approach to model a blood products distribution system over a certain horizon. The objective is to determine for each period of the planning horizon, the quantities of products to deliver and collect as well as the routing to be performed by each vehicle in order to minimize the total transportation and storage cost without allowing shortages. We present a brief review of literature related to our problem and we provide a mathematical model that takes into account the constraint of perishability.

Paper Nr: 39
Title:

Dynamic Multi-trip Vehicle Routing with Unusual Time-windows for the Pick-up of Blood Samples and Delivery of Medical Material

Authors:

Nicolas Zufferey, Byung Yun Cho and Rémy Glardon

Abstract: Given a fleet of identical vehicles and a set of n clients to be served from a single depot, the well-known vehicle routing problem (VRP) consists in serving each client (with a deterministic demand) once with a unique vehicle, with the aim of minimizing the total traveled distance. In this work, the basic VRP is extended within a medical environment, leading to MVRP (for medical VRP). Indeed, the depot is typically a laboratory for blood analysis, and a client is assumed to be a medical location at which blood samples should be picked up by a vehicle. In order to have efficient tests at the laboratory, at most 90 minutes should elapse between the release time of the blood sample and the delivery time at the laboratory. In addition, only a proportion of the demand is known in advance and the travel times depend on the traffic conditions. A fleet of non-identical vehicle is considered (with different speeds and capacities), and each location has to be visited anytime a blood sample is available. Finally, medical items should be daily delivered from the laboratory to some medical locations. A transportation cost function with three components has to be minimized. Solution methods are proposed, which are able to account for all the specific features of the problem. The experiments highlight the benefit of considering diversion opportunities (which consists in diverting a vehicle away from its planned destinations).

Paper Nr: 62
Title:

Prize Collecting Travelling Salesman Problem - Fast Heuristic Separations

Authors:

Kamyar Khodamoradi and Ramesh Krishnamurti

Abstract: The Prize Collecting Travelling Salesman Problem (PCTSP) is an important generalization of the famous Travelling Salesman Problem. It also arises as a sub problem in many variants of the Vehicle Routing Problem. In this paper, we provide efficient methods to solve the linear programming relaxation of the PCTSP. We provide efficient heuristics to obtain the Generalized Subtour Elimination Constraints (GSECs) for the PCTSP, and compare its performance with an optimal separation procedure. Furthermore, we show that a heuristic to separate the primitive comb inequalities for the TSP can be applied to separate the primitive comb inequalities introduced for the PCTSP. We evaluate the effectiveness of these inequalities in reducing the integrality gap for the PCTSP.

Paper Nr: 63
Title:

Constrained Portfolio Optimisation: The State-of-the-Art Markowitz Models

Authors:

Yan Jin, Rong Qu and Jason Atkin

Abstract: This paper studies the state-of-art constrained portfolio optimization models, using exact solver to identify the optimal solutions or lower bound for the benchmark instances at the OR-library with extended constraints. The effects of pre-assignment, round-lot, and class constraints based on the quantity and cardinality constrained Markowitz model are firstly investigated to gain insights of increased problem difficulty, followed by the analysis of various constraint settings including those mostly studied in the literature. The study aims to provide useful guidance for future investigations in computational algorithms.

Paper Nr: 65
Title:

Verifying Geostatistical Travel Time Properties on Routing Networks

Authors:

Renaud De Landtsheer and Christophe Ponsard

Abstract: Nowadays, many systems are increasingly relying on interconnected, geolocated, and mobile devices. In order to cope with this, geographical information system (GIS) have evolved to precisely capture not only the spatial characteristics of real world transportation networks but also temporal dimension, including the variability of travel duration related to traffic jams. This paper explores the verification of a number of interesting spatiotemporal properties identified from a set of real world cases and expressed on enriched GIS data structures. It details our progress on developing efficient algorithmic modules to verifying such properties. We have applied our algorithms on the medical emergency infrastructures deployed in Belgium.

Paper Nr: 69
Title:

A New Modelling Approach Is Required to Help Mobile Network Operators Handle the Growing Demand for Data Traffic

Authors:

Leonardo Lamorgese, Tomas Eric Nordlander and Carlo Mannino

Abstract: Last year, global mobile data traffic grew by 69%, and similar growth rates are expected in the coming years. This growth affects the quality of service, and mobile network operators are finding it increasingly difficult to manage mobile data traffic. To this end, they are drastically increasing the number of sites and antennae, as well as modernising existing networks. This requires selecting the best antenna locations in terms of service area coverage, spectrum availability, installation costs, demographics, etc. In addition, when extending the wireless network with new antennae, the radio-electrical parameter settings of new and neighbouring antennae require (re)calibration to minimise interference—a process that in principle may affect the entire network. Moreover, the antennae must connect to the core network and influence it. This complex optimisation planning problem does not lend itself well to a manual solution approach. Still, these plans are developed “manually”, with the support of IT tools, through a time-consuming and inefficient trial-and-error process. Applied optimisation is needed to tackle this problem effectively, but this requires advancing the state-of-the-art: Most papers focus on solving the different sub-problems independently. However, these affect each other heavily and they must be considered simultaneously to maximise the offered service: optimising the location and configuration of new antennae and the configuration of wireless network radio-electrical parameters, while taking into account access to the core network.

Paper Nr: 70
Title:

Large Scale Petrol Station Replenishment Problem with Time Windows: A Real Case Study

Authors:

Pablo A. Villegas and Víctor M. Albornoz

Abstract: In this study we deal with a real case of the problem known as Petrol Station Replenishment Problem with Time Windows arising in Chile. The company involved is one of the biggest actors in the country, and every day must schedule a series of trips from their depots to their clients, delivering different kinds of fuel. This specific case has some differences from prior formulations of this problem (e.g. trucks works in shifts with hard time windows). Also, another challenge is the high number of orders and trucks involved in everyday planning. To solve this problem in reasonable computing times we propose a sequential insertion heuristic. Finally, we present results over a month of data.

Paper Nr: 72
Title:

Short-term Production Scheduling in the Soft Drink Industry

Authors:

Javier Cuzmar Leiva and Víctor M. Albornoz

Abstract: In this study, the formulation of a mixed-integer linear programming model applied to production scheduling in the soft drink industry is addressed. The model considers the production of beverages with different flavors and formats in two synchronized production stages: preparation of syrup in storage tanks and bottling syrup in packaging lines. This model defines the order of the products at each stage of production with makespan minimization, taking into account aspects such as sequence-dependent set-up times, synchronisation between production stages, several tanks and packaging lines, capacity constraints, time constraints (deadlines). Also considered is the property of job splitting in first stage, which reduces waiting times in the packaging lines. We include the method of application in a real-world problem of a beverage bottling company. The results show that on average the application managed to improve 15.67% the company’s current solution.

Paper Nr: 75
Title:

An Iterated Greedy Heuristic for the 1/N Portfolio Tracking Problem

Authors:

Oliver Strub and Norbert Trautmann

Abstract: The 1/N portfolio represents a simple strategy to invest money in the stock market. Investors who follow this strategy invest an equal proportion of their investment budget in each stock from a given investment universe. Empirical results indicate that this strategy leads to competitive results in terms of risk and return compared to more sophisticated strategies. However, in practice, investing in all N stocks from a given investment universe can cause substantial transaction costs if N is large or if the market is illiquid. The optimization problem considered in this paper consists of optimally replicating the returns of the 1/N portfolio by selecting a small subset of the N stocks, and determining the respective weight for each selected stock. For the first time, we apply the concept of iterated greedy heuristics to this novel portfolio-optimization problem. For analyzing the performance of our heuristic approach, we also formulate the problem as a mixed-integer quadratic program (MIQP). Our computational results indicate that, within a limited CPU time, our heuristic approach outperforms the MIQP, in particular when the number of stocks N grows large.

Posters
Paper Nr: 4
Title:

Bayesian Inventory Planning with Imperfect Demand Estimation in Online Flash Sale

Authors:

Ted Tao Yuan, Michelle Cai and Daniel Kao

Abstract: Daily deal, or flash sale, websites offer limited quantity of selected brands and products for a short period of time. The idea is that short-term sales event of branded products drives consumer interest. Flash sale sites like vip.com negotiate great deals from various vendors on a limited quantity of selected products. In operation, all merchandises need to be allocated to regional warehouses before a short-term sales event starts. The variety and quantity of merchandises change significantly from one sales event to another. Unsold items are typically shipped back to vendors after the sales event ends. In this paper, we discuss the design and implementation of a regional warehouse merchandise allocation model and strategy to maximize sales conversion rate. Our work reveals the uniqueness of inventory planning of flash sale and its similarity to that of general online retailers. Our machine learning prediction models and Bayesian Updating strategy are highly valuable to the improvement of regional warehouse efficiency and customer experience in dealing with highly volatile flash sale inventory.

Paper Nr: 36
Title:

Optimization of Routes for Hazardous Materials Transportation - A Case Study of Fuel Deliveries in Lisbon

Authors:

Duarte Correia, Marta Castilho Gomes, Alexandre B. Gonçalves and Sílvia Shrubsall

Abstract: This study aims at contributing to increase road safety by expanding knowledge on how to identify safe urban routes for Hazardous Materials that are commercially doable. A bi-level linear model was implemented in GAMS modelling software considering fuel distribution data and the road network for the city of Lisbon. Its first level consists in road risk minimization whereas the second level aims at maintaining the economic viability of the itineraries. This work expands the research of Rodrigues et al. (2015) by increasing: (1) the comprehensiveness of the road data, and (2) the complexity of the analysis by including, besides resident population, hospital and school users potentially affected by an accident, and by comparing different itineraries and the computational time needed to solve the model. The work analyses much more comprehensive data than those found in previous studies in the literature and was successful in identifying optimal solutions, most of which in short computational time. This suggests that this methodology can be used by the industry to identify routes for fuel distribution in urban environments. In the future, the routes generated by the model will be compared with routes currently used in fuel distribution.

Paper Nr: 37
Title:

Optimization of Routes for Road Surface Inspection - An Application to the Portuguese National Road Network

Authors:

Filipe F. Gomes, Marta Castilho Gomes and Alexandre B. Gonçalves

Abstract: Infraestruturas de Portugal S.A. (IP) is responsible for managing the Portuguese rail network infrastructure and a significant part of the road network. An annual inspection must be performed on every road segment for which IP is responsible, which sums up around 14,000 km. This is a costly operation regarding time, human and monetary resources. An optimization model that incorporates the problem technical constraints was developed and a cost analysis performed to compare the distinct scenarios that IP may face in the general layout of the inspection programme.

Paper Nr: 43
Title:

Preventive Replacement Policies with Aging Failure and Third-part Damage

Authors:

Xufeng Zhao, Khalifa N. Al-Khalifa and Abdel Magid Hamouda

Abstract: In general, corrosions, degrading the mechanical strength of pipelines gradually with its age in a stochastic way, is the predominant cause of pipeline leaks. In addition, the third-part damage is the leading cause of pipeline ruptures, which occurs randomly in a statistical sense. Naturally, corrective replacement (CR) is done immediately when the pipeline is subjected to a random failure. To reduce the failure probabilities, preventive replacement (PR) policies are scheduled to meet the failure due to aging and the third-part damage. We model three PR policies, using the renewal theory in reliability, and obtain their optimal solutions analytically to minimize respective replacement cost rates. Finally, numerical examples are given to compare these policies.