Contributed Session Tue.3.H 0106

Tuesday, 15:15 - 16:45 h, Room: H 0106

Cluster 13: Logistics, traffic, and transportation [...]

Exact approaches to routing problems


Chair: Stefan Ropke



Tuesday, 15:15 - 15:40 h, Room: H 0106, Talk 1

Vladimir Deineko
A framework for vehicle routing


We consider the capacitated vehicle routing problem (VRP) and various modifications of this problem. We suggest a general framework which is flexible enough to be used for all these modifications of the VRP. The main algorithm behind the framework is the well-known Held & Karp dynamic programming algorithm for the travelling salesman problem.
Results of computational experiments on the known benchmark problems show the competitiveness of our approach with the best known heuristics.



Tuesday, 15:45 - 16:10 h, Room: H 0106, Talk 2

Carlos Cardonha
A fast solution method applied to the vehicle positioning problem and its multi-periodic, online, and robust extension

Coauthor: Ralf Borndörfer


The Vehicle Positioning Problem (VPP) is a classical and challenging combinatorial optimization problem that deals with the assignment of vehicles of a transport company to parking positions.
In this talk, we present an exact solution technique that explores partial knowledge about the likelihood of having certain variables in optimal solutions in order to produce feasible solutions for MIPs quickly. We present an exact algorithm for the VPP based on this method and show through computational experiments that it is able to provide optimal solutions for large-scale scenarios of the problem. We also show that some important extensions of the VPP - namely, its multi-periodic version, which was previously intractable, and its online version - can be solved efficiently with this method. Finally, we also discuss how one can apply the concept of robustness to the problem and how robust solutions can be efficiently computed for the VPP.



Tuesday, 16:15 - 16:40 h, Room: H 0106, Talk 3

Stefan Ropke
Exact and heuristic solution methods for the generalized asymmetric vehicle routing problem and the capacitated arc routing problem


In the generalized asymmetric vehicle routing problem (GAVRP) one is given a set of nodes consisting of customer nodes and a depot. Customer nodes are partitioned into clusters and one must construct a number of routes, starting and ending at the depot, such that exactly one customer from each cluster is visited. Each cluster has a certain demand and routes must be constructed such that the total demand on a route is below a given threshold. We solve the GAVRP with an exact method, based on the branch-and-cut-and-price paradigm, as well as with a parallel adaptive large neighborhood search heuristic. Furthermore, in [Baldacci, Bartolini and Laporte (2010)] it was shown how an instance of the capacitated arc routing problem (CARP) easily could be transformed into a GAVRP instance. We use this transformation in order to solve CARP instances with the proposed GAVRP algorithms and report on extensive computational experiments for both problem types.


  There are three major facts that should be watched out for in all payday loans in the United States. In this section we give only a brief summary recommendation for admission of Levitra. Full information can be found in the instructions for receiving medications with vardenafil.