ROUTE 2005 was the third edition of an International Workshop on Vehicle Routing, Intermodal Transportation, and related areas that took place at the University of Bologna Residential Center of Bertinoro, Italy, between June 23rd and June 26th, 2005. The previous editions of the workshop were held in Denmark in 2000 and 2003, organized by Prof. Oli B.G. Madsen of the Technical University of Denmark.
The workshop aimed at providing a high level forum for scientific exchange and cooperation in the routing and transportation area. To this end, and according to the style set up for the previous editions of ROUTE workshop, about 40 of the most active researchers in routing and transportation were invited to contribute to ROUTE 2005 and present their most recent and relevant results. The 27 presentations, which were scheduled in a single stream during the 4 days of the workshop, covered almost all the methodological approaches and the classical and emerging problems in the field: from exact algorithms to new heuristics and metaheuristics, from the capacitated Vehicle Routing Problem (VRP), to Arc Routing Problems, to stochastic VRPs and to relevant case studies including complex practical problems.
The overall level of the scientific contributions presented at ROUTE 2005 has been fairly high. This definitely convinced us to accept the kind offer of Bruce Golden to collect some of the presented papers in this special issue of Networks. The response from the participants was enthusiastic, so we were able to finalize this project in which seven of the best papers presented at the conference were collected.
The structure of the special issue reflects the richness of the contributions presented at the workshop. For example, with respect to methodological approaches, out of the seven papers in this special issue the first three present exact algorithms, whereas the last four describe and analyze heuristics and metaheuristics. In the following, we comment on each paper, starting with the first part that is devoted to exact approaches.
The first paper, by CorberΓ‘n, Plana, and Sanchis, introduces an exact cutting-plane algorithm for the Windy General Routing Problem (WGRP). This problem generalizes a huge set of important Arc Routing Problems with directed and undirected arc costs. The authors present an ILP model, generalize to WGRP the various classes of facet-inducing inequalities proposed for Arc Routing Problems and discuss the associated separation procedures. The approach is extensively tested on various classes of large-size test instances, including up to 1,000 nodes and thousands of arcs, and shows consistently good results on the various important Arc Routing Problems that WGRP includes as special cases.
The paper by Ropke, Cordeau, and Laporte proposes two integer programming models for the Pickup and Delivery Problem with Time Windows (PDPTW) and the closely related Dial-a-Ride Problem (DARP). The formulations are strengthened by means of several families of valid inequalities that are used within a branch-and-cut algorithm for the exact solution of these problems. The approach has been extensively tested on several instance sets for both PDPTW and DARP, being able to solve to optimality instances with up to 96 requests.
The last paper presenting exact methods is that of Kallehauge, Boland, and Madsen that deals with the VRP with Time Windows (VRPTW), which is tackled for the first time with a branch-and-cut approach. The authors describe a new formulation based on a directed graph that uses strengthened infeasible-path inequalities to introduce capacity and time window constraints. The VRPTW polytope is studied, and conditions under which the lifted path inequalities are facet defining are derived. The branch-and-cut algorithm is tested on the classical benchmark instances and it appears to be competitive with the best existing exact approaches, for at least the small-size instances.