Journées de l'optimisation 2007 Optimizations days

In this paper we present a new exact algorithm for the Capacitated Vehicle Routing Problem (CVRP) based on the set partitioning formulation with additional cuts that correspond to capacity and clique inequalities. We describe a bounding procedure that finds a near optimal dual solution of the LP-relaxation of the resulting mathematical formulation by combining three dual ascent heuristics. The first dual heuristic is based on the q-route relaxation of the set partitioning formulation of the CVRP. The second one combines Lagrangean relaxation and column/cut generation and the third attempts to close the duality gap left by the first two procedures using a classical column/cut generation technique. The final dual solution is used to generate a reduced problem containing only the routes whose reduced costs are smaller than the gap between an upper bound and the lower bound achieved. The resulting problem is solved by an integer programming solver. Computational results over the main instances from the literature show the effectiveness of the proposed algorithm.

We explore heuristics for the vehicle routing problem with multiple trips (VRPM). Unlike the classical vehicle routing problem, the VRPM permits vehicles to make multiple trips to and from a central depot within a given time duration. We begin by constructing routes via a petal heuristic. These routes are then combined to form a large number of linked routes. In contrast to previous research on the VRPM, which predominantly takes a bin-packing approach to route linking, we explicitly combine routes within the route duration limit. We then obtain a solution by solving a large scale set covering problem to select a subset of these routes. Finally, we present the results of this approach and compare them to those of other VRPM solution methodologies.

The decision about the adequate fulfilment mode of consecutively arriving requests is a basic task of the operation transport planning. From the two modes self fulfilment (with own equipment) or subcontracting (deploying a service partner) the cheaper one is typically selected. However, in some unpredictable situations it is appropriate to deviate from this minimal cost strategy and to prefer the more expensive but more reliable mode of transport. In this contribution, we discuss general strategies to code such a strategy in an online optimization model. Furthermore, we propose generic models that adapt themselves to the current system state by modifying the search direction (objective) as well as the search space in order to consider not only cost criteria but reliability issues as well. The general applicability of such an approach is evaluated in comprehensive numerical results.

This study analyzes the problem of maximizing the profit collected by a traveling service facility that performs a tour. The facility collects the whole profit from the visited cities and partial profit from unvisited cities, which depends on the attractiveness of the visited cities and distance from the visited cities.