Premium
Routing with time windows by column generation
Author(s) -
Desrosiers Jacques,
Soumis François,
Desrochers Martin
Publication year - 1984
Publication title -
networks
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.977
H-Index - 64
eISSN - 1097-0037
pISSN - 0028-3045
DOI - 10.1002/net.3230140406
Subject(s) - column generation , vehicle routing problem , trips architecture , travelling salesman problem , interval (graph theory) , shortest path problem , mathematical optimization , computer science , simplex , routing (electronic design automation) , set (abstract data type) , generalization , mathematics , graph , combinatorics , computer network , theoretical computer science , parallel computing , programming language , mathematical analysis
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 its given time 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 ‐traveling salesman problem. We use column generation on a set partitioning problem solved by simplex and branch‐and‐bound; columns are generated by a shortest path algorithm with time windows on the nodes. Numerical results for several school bus transportation problems with up to 151 trips are discussed.