Groupe d’études et de recherche en analyse des décisions


Routing and Scheduling by Branch-and-Bound on Time Windows

, , et

Consider a set of trips where each trip is specified a priori by a place of origin, a destination, a duration, a cost and a time interval within which the trip must begin. The trips may include visits to one or more specific points. Our problem is to determine the number of vehicles required together with their routes and schedules, so that each trip begins within his given interval, while the fixed costs related to the number of vehicles, and the travel costs between trips are minimized. The problem is a generalization of the m-travelling salesman problem.

We compare numerical results for two algorithms:
1) Adaptation of the Carpaneto-Toth algorithm for the asymmetric travelling salesman problem: solution of network problems by relaxing scheduling constraints, and branch-and-bound on flow variables.
2) Solution of network problems by relaxing scheduling constraints and branch-and-bound based on dividing the time windows.

, 22 pages