Skip to Main content Skip to Navigation
New interface
Journal articles

Generating feasible schedules for a pick-up and delivery problem

Eric Domenjoud 1 Claude Kirchner 1 Jianyang Zhou 1 
1 PROTHEO - Constraints, automatic deduction and software properties proofs
INRIA Lorraine, LORIA - Laboratoire Lorrain de Recherche en Informatique et ses Applications
Abstract : In this research, we study a transportation problem that involves vehicle routing and driver scheduling for a bus station. The problem requires drivers to provide pick-up and delivery services to customers. Its solution involves planning itineraries for buses and establishing working schedule for drivers,subject to vehicle capacity limitation and time constraints. The objective is to efficiently schedule the fleet of vehicles for customer demand so as to reduce costs. This paper presents a complete constraint model and a solution method for solving the problem. For vehicle routing, a permutation constraint is used to impose a total order for visiting all customer locations regardless of different vehicle routes. This provides a global planning over all routes and plays an important role in the solution method. For driver scheduling, set partitioning constraints are used for assigning drivers and vehicles to requests. Based on this constraint model, efficient reactive planning and optimization algorithms are constructed to generate feasible schedules for the problem.
Document type :
Journal articles
Complete list of metadata
Contributor : Publications Loria Connect in order to contact the contributor
Submitted on : Tuesday, September 26, 2006 - 8:40:12 AM
Last modification on : Friday, February 4, 2022 - 3:31:28 AM


  • HAL Id : inria-00098910, version 1



Eric Domenjoud, Claude Kirchner, Jianyang Zhou. Generating feasible schedules for a pick-up and delivery problem. Electronic Notes in Discrete Mathematics, 1999, 1. ⟨inria-00098910⟩



Record views