Invited Session Wed.1.H 0106

Wednesday, 10:30 - 12:00 h, Room: H 0106

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

Vehicle routing and logistics optimization


Chair: Daniele Vigo



Wednesday, 10:30 - 10:55 h, Room: H 0106, Talk 1

Mario Ruthmair
An adaptive layers framework for vehicle routing problems

Coauthor: G√ľnther R. Raidl


Current exact solution methods for vehicle routing problems are mostly based on set partitioning formulations enhanced by strong valid inequalities. We present a different approach where resources, e.g., capacities or times, are modeled on a layered graph in which the original graph is duplicated for each achievable resource value. MIP models on this layered graph typically yield tight LP bounds. However, as the size of this graph strongly depends on the resource bounds, such models may be huge and impracticable. We propose a framework for approximating the LP bound of such a resource-indexed formulation by a sequence of much smaller models. Based on a strongly reduced node set in the layered graph we redirect arcs in a way to obtain lower and upper bounds to the LP value of the complete model. This reduced layered graph is iteratively extended, decreasing the gap. Moreover, a sequence of improving primal bounds can be provided. The final model extended by inequalities to ensure feasibility is solved by branch-and-cut. Obtained results, e.g., for the vehicle routing problem with time windows, look promising although we currently cannot compete with state-of-the-art methods.



Wednesday, 11:00 - 11:25 h, Room: H 0106, Talk 2

Roberto Roberti
Dynamic NG-path relaxation

Coauthors: Roberto Baldacci, Aristide Mingozzi


We recently introduced a new state-space relaxation, called ng-path relaxation, to compute lower bounds to routing problems. This relaxation consists of partitioning the set of all possible paths ending at a generic vertex according to a mapping function that associates with each path a subset of the visited vertices that depends on the order in which such vertices are visited.
In this talk, we propose a new dynamic method to improve the ng-path relaxation which consists of defining, iteratively, the mapping function of the ng-path relaxation using the results achieved at the previous iteration. This method is analogous to cutting plane methods, where the cuts violated by the ng-paths at a given iteration are incorporated in the new ng-path relaxation at the next iteration.
The new technique has been used to solve the traveling salesman problem with cumulative costs (CTSP) and to produce new benchmark results for the TSPTW. The results obtained show the effectiveness of the proposed method.



Wednesday, 11:30 - 11:55 h, Room: H 0106, Talk 3

Daniele Vigo
An exact approach for the clustered vehicle routing problem

Coauthors: Maria Battarra, Gunes Erdogan


We present an exact approach for the clustered vehicle routing problem (Clu-VRP),which is a generalization of the capacitated vehicle routing problem (CVRP), in which the customers are grouped into clusters. As in the CVRP, all the customers must be visited exactly once, but a vehicle visiting one customer in a cluster must visit all the remaining customers in the cluster before leaving it. An integer programming formulation for the Clu-VRP based on an exponential time preprocessing scheme is presented. The linear relaxation of the formulation is strengthened in a branch & cut algorithm by including valid inequalities for the CVRP. Computational experiments on instances adapted from the literature and real-world problems are presented.


  The majority of financial loan companies provide the service of getting North Carolina Loans Online for U.S. citizens. The main active actual substance of Levitra Professional online - Vardenafil does not affect the seminal fluid and is not addictive.