Venue: H10-31
Time: 12:00
Florian Arnold (University of Antwerp)
16 September 2016
Generating problem-specific knowledge (for the Vehicle Routing Problem)
Abstract:
The Vehicle Routing Problem (VRP) is probably the most-studied problem in Operations Research. However, in the race for faster algorithms and better solutions, few research has been performed to shed light on the problem itself. Even though problem specific knowledge is an important ingredient in the design of heuristics, such knowledge is rare for the VRP. As an example, it is proven that in the Traveling Salesman Problem does no optimal solution contain intersecting edges. Even though such a statement is not true for the VRP, it should be possible to deduct general guidelines such as: "In general, solutions can be improved by removing intersections". In this presentations, we take a first step in this direction and use data mining techniques to identify properties that distinguish optimal from non-optimal solutions. Those properties describe the geometrical nature and relations of routes. We combine them with instance characteristics to derive findings that are independent of the specific problem instance. With the help of a classification learner we are able to predict with a relatively high percentage from the defined properties whether a certain solution for any instance is optimal or not. Moreover, we extract rules that explain why a solution is not optimal. Finally, we demonstrate how these rules can be used in the design of heuristics. We implement a local search technique that uses a rule-database to determine the most-promising moves in each step.
Corinne Luteyn (Centre for Industrial Management/Traffic & Infrastructure, KU Leuven)
23 September 2016
Improving an Incomplete Road Network by small Arc Changes
Abstract:
In most Routing Problems, it is assumed that the considered road network is complete and fixed. However, in practice, this is usually not the case. Most existing road networks are, for example, incomplete, since there is no direct connection between each pair of locations. In this research, the possibility to improve an incomplete road network by some small arc changes is investigated. Three possible changes are studied in this research: (re-)opening pedestrian zones for vehicles, widening existing roads and converting existing roads into one-way roads with a higher speed. Different procedures are proposed to find the best improvement such that the total travel time of the vehicles on the network is minimized. This improvement can be the best single change or the best set of changes given a budget constraint. The first procedure combines a construction part and an analysis part with a testing stage. During the construction part, routes for the vehicles are constructed in the existing network using a fast Variable Neighborhood Search. In the second part of the heuristic, the constructed routes are analyzed heuristically in order to determine a good improvement for the network. Since the selected improvements in a set can interfere with each other, the determined improvement is tested during the testing stage. The second approach is an Adaptive Large Neighborhood Search of which the main structure is based on a Simulated Annealing algorithm. New solutions are generated by a large neighborhood, which consists of a set of destroy and a set of repair methods. To test the proposed procedure, 32 benchmark instances are constructed from a real road network. These benchmark instances have one up to four vehicles available to serve 20 up to 150 customers. Based on the experiments on these test networks can be concluded that improving an incomplete road network by a single change leads in average to a reduction in travel time of about 1.5%. Furthermore, if the network is improved by a set of changes given a budget allowing a combination of around three improvements, the average reduction is about 5%.
Harwin de Vries (Erasmus School of Economics)
7 October 2016
Optimizing Population Screening for Infectious: The Case of HAT Disease Control in D.R. Congo
Abstract:
Population screening by mobile units is crucial to control several infectious diseases. We consider the following planning problem: given a set of populations at risk, the expected evolution of the epidemic in these populations, and a fixed number of mobile units, which villages should be screened when? We present descriptive models for the development of the burden of disease over time which take screening explicitly into account, use these to develop planning policies, and numerically analyze them in the context of the control of sleeping sickness (HAT) in D.R. Congo.
Charlie Ye (Erasmus School of Economics)
21 October 2016
Participation behavior and social welfare in repeated task allocations
Abstract:
Task allocation problems have focused on achieving one-shot optimality. In practice, many task allocation problems are of repeated nature, where the allocation outcome of previous rounds may influence the participation of agents in subsequent rounds, and consequently, the quality of the allocations in the long term. We investigate how allocation influences agents' decision to participate using prospect theory, and simulate how agents' participation affects the system's long term social welfare. We compare two task allocation algorithms in this study, one only considering optimality in terms of costs and the other considering optimality in terms of primarily fairness and secondarily costs. The simulation results demonstrate that fairness incentivizes agents to keep participating and consequently leads to a higher social welfare.
Maaike Hoogeboom (VU Amsterdam)
4 November 2016
The Vehicle Routing Problem with arrival time diversification
Abstract:
Cash in Transit (CIT) companies deliver valuable goods to banks, ATMs and stores. Legal regulations and security considerations force these companies to take various measures to protect their valuable cargo against attacks. Driving varying routes to serve their customers is one key strategy to lower the risk of an attack. In this research, we want to generate sufficiently unpredictable routes by varying the arrival time at a customer, while minimizing transportation costs. We present a novel solution approach, by removing previous arrival time slots at customers from the solution space. This results in a routing problem with multiple time windows in which the customers are still available for service. The problem is solved using a rolling horizon framework by taking into account previous arrival times at the customers. Since waiting time at a customer is not allowed due to safety reasons, an efficient method is proposed to check if a route is feasible. An iterated tabu search is used to solve the routing problem and the proposed solution approach is tested on benchmark instances from the literature. We were able to find new best solutions for all but one instance and we study the trade-off between arrival time diversification and transportation cost.
Rolf van Lieshout (Erasmus School of Economics)
2 December 2017
The Vehicle Rescheduling Problem with Retiming
Abstract:
When a vehicle breaks down in a transportation system, the remaining vehicles can be rescheduled to minimize the impact of the breakdown. In this paper, we discuss the vehicle rescheduling problem with retiming (VRSPRT). To incorporate delays, we expand the recovery network with retiming possibilities. As the network gets too large, we propose an iterative neighborhood exploration heuristic to solve the VRSPRT. Experiments show that by delaying one or two trips with on average 4 minutes, we can decrease the average number of cancelled trips with 30 percent.
Information
Remy Spliet
Room: 11-05
Phone: 010-4081342
E-mail: spliet@ese.eur.nl