Literatur

1

H.A. Eiselt, Michel Gendreau, and Gilbert Laporte.
Arc routing problems. I: The Chinese postman problem.
Operations Research, 43(2):231-242, 1995.

Arc routing problems arise in several areas of distribution management and have long been the object of study by mathematicians and operations researchers. In the first of a two-part survey, the Chinese postman problem (CPP) is considered. The main algorithmic results for the CPP are reviewed in five main sections: the undirected CPP, the directed CPP, the windy postman problem, the mixed CPP, and the hierarchical CPP.

2

H.A. Eiselt, Michel Gendreau, and Gilbert Laporte.
Arc routing problems. II: The rural postman problem.
Operations Research, 43(3):399-414, 1995.

This is the second half of a two-part survey on arc routing problems. Here, the rural postman problem (RPP) is reviewed. The paper is organized as follows: applications, the undirected RPP, the directed RPP, the stacker crane problem, and the capacitated arc routing problem.

3

Yves Nobert and Jean-Claude Picard.
An optimal algorithm for the mixed Chinese postman problem.
27(2):95-108, 1996.

The Chinese postman problem is well solved when the original graph contains only arcs or only edges. The mixed Chinese postman problem (MCPP) is, however, NP-complete, and very few papers have been devoted to this problem. In this paper, we present a new integer programming model and a new optimal algorithm for the MCPP. The simplex method is used iteratively to obtain sharp lower bounds by solving successive relaxations of this model. Optimality is achieved by using Gomory cuts, blossom inequalities and balanced set constraints. Detailed computational results are presented.

4

A. Corberán and J.M. Sanchis.
About Mixed Chinese Postman Problems.
Discussion paper durig the meeting in Valencia, December 1999, 1999.

5

A. Corberán and J.M. Sanchis.
A polyhedral approach to the rural postman problem.
European Journal of Operations Research, 79:95-114, 1994.

We study the polyhedron associated with the Rural Postman Problem (RPP). Because the RPP is NP-hard, we cannot expect to find a complete description of the rural postman polyhedron of a general graph, but a partial knowledge of such a description frequently proves to be useful for both theoretical and computational purposes. We have tried to characterize the facial structure of this unbounded full-dimensional polyhedron. Sets of valid inequalities inducing facets have been studied as well as their use in a cutting-plane algorithm. The application of this algorithm to a set of RPP instances taken from the literature and two instances of larger size taken from a real world graph is described. All these instances were solved to optimality.

6

Marshall Fisher.
Vehicle Routing.
In M.G. Ball, T. L. Magnanti, C. L. Monma, and G. L. Nemhauser, editors, Network Routing, volume 8 of Handbooks in operations research and management science, chapter 1, pages 1-33. Elsevier, 1995.

The vehicle routing problem is to determine K vehicle routes, where a route is a tour that begins at the depot, traverses a subset of the customers in a specified sequence and returns to the depot. Each customer must be assigned to exactly one of the K vehicle routes and the total size of deliveries for customers assigned to each vehicle must not exceed the vehicle capacity b. The routes should be chosen to minimize total travel cost.

This chapter will present the most important algorithms that have been developed for this model. However, before plunging into the mathematical development, it will be helpful to consider some examples of vehicle routing problems and various practical issues that arise in the use of vehicle routing models.

7

P. Augerat, J. M. Belenguer, E. Benavent, A. Corberán, and D. Naddef.
Separating Capacity Constraints in the CVRP Using Tabu Search.
unpublished.

8

Michel Gendreau, Gilbert Laporte, and Jean-Yves Potvin.
Vehicle routing: Modern heuristics.
In E. Aarts and J.K. Lenstra, editors, Local Search in Combinatorial Optimization, chapter 9, pages 311-336. Wiley, 1997.

The vehicle routing problem may be stated as follows. Customers at different locations must be served by m identical vehicles. m may be fixed or can be freely chosen. One has to determine m vehicle routes of minimal total cost, each starting and ending at a depot, so that every customer is visited exactly once, subject to a number of side constraints: (1) A weight may be associated with each customer and the sum of weights of the customers visited by each vehicle must not exceed the vehicle capacity. (2) The travel time of any vehicle must not exceed a given bound. (3) The customers must be visited within specific time windows.

The following types of local search heuristics for these types of problems are surveyed and compared: simulated annealing, tabu search, genetic algorithms, and algorithms using neural networks. For each type of heuristics computational results are reported. Furthermore the different types of heuristics are compared with each other.