×

Column generation techniques for pickup and delivery problems. (English) Zbl 0833.90037

Eindhoven: Techn. Univ. Eindhoven, v, 121 p. (1994).
This paper is a doctoral dissertation that is devoted to pickup and delivery problems. A pickup and delivery problem is a vehicle routing and scheduling problem in which a set of vehicles is available to serve a set of requests. It is, however, different from the traditional vehicle routing problem in the sense that each request specifies locations to be picked up and to be delivered by the vehicle. Pickup and delivery problems arise in a dial-a-ride system, and manufacturing systems.
This paper consists of 4 chapters. Chap. 1 defines the general pickup and delivery problem. Chap. 2 discusses the resource assignment problem of assigning requests to vehicles for which a set partitioning model is used, and a branch-and-price algorithm that uses an LP relaxation with column generation and a branch-and-bound technique is developed. The problem is generalized to the one with time windows in Chap. 3. Chap. 4, based on the above algorithm, develops a planning tool DRIVE (Dynamic Routing of Independent VEhicles) for a practical material distribution problem that motivated this study.
Reviewer: H.Kise (Kyoto)

MSC:

90B06 Transportation, logistics and supply chain management
90B35 Deterministic scheduling theory in operations research
PDFBibTeX XMLCite