Journées de l'optimisation 2007 Optimizations days

In the m-Peripatetic Salesman Problem (m-PSP) the aim is to determine m edge disjoint Hamiltonian cycles of minimum total cost on a graph. This presentation introduces a new formulation with two types of variables: the classical edge variables and new edge-edge variables. A branch-and-cut algorithm for the m-PSP according to this formulation and some numerical results on randomly generated and TSPLIB Euclidean instances are presented.

Over the past decade, cross docking has emerged as a material handling technology in transportation. As a variation of the well-known Vehicle Routing Problem (VRP), the Vehicle Routing Problem with Cross-Docking (VRPCD) becomes a realistic problem in the logistic planning of the supply chain management. This paper addresses the VRPCD, where a set of homogenous vehicles are used to transport goods from the suppliers to the corresponding customers via a cross dock. The goods can be consolidated at the cross dock but cannot be stored during the night as the cross dock does not have the inventory-holding function. The objective of VRPCD is to minimize the total travelling distance while the time windows for each supplier/customer and the time horizon for the whole transportation operation are respected. In this paper, a Mixed Integer Programming formulation for the VRPCD is proposed. A tabu search heuristic based on Cordeau et al. (2001) is embedded in an adaptive memory procedure for solving the problem. The proposed algorithm is implemented and tested on the data provided by Transvision involving up to 200-pair nodes. The preliminary results show that, this algorithm can solve the problem within reasonable computational time.

Given a fleet of vehicles assigned to a single depot, the vehicle routing problem with time windows (VRPTW) consists of determining a set of feasible vehicle routes to deliver goods to a set of customers while minimizing, first, the number of vehicles used and, second, total mileage. A large number of heuristic approaches for the VRPTW have been proposed in the literature, but none have taken advantage of the power of branch-and-price which is the leading methodology for the exact solution of the VRPTW. In this paper, we present a large neighborhood search algorithm that relies on a heuristic branch-and-price method for neighborhood exploration. To ensure diversification during the search, this approach uses different procedures for defining the neighborhood to explore at each iteration. Computational results on the Solomon's and Homberger's benchmark instances will be reported.