Routing with time windows by column generation. (English) Zbl 0571.90088

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.


90C35 Programming involving graphs or networks
90B35 Deterministic scheduling theory in operations research
65K05 Numerical mathematical programming methods
90C08 Special problems of linear programming (transportation, multi-index, data envelopment analysis, etc.)
90C10 Integer programming
Full Text: DOI


[1] Bellmore, Operations Res. 19 pp 278– (1971)
[2] Bodin, Comput. Operations Res. 10 pp 69– (1983)
[3] Bratley, Naval Res. Logistics Quart. 22 pp 165– (1975)
[4] Christofides, Networks 11 pp 145– (1981)
[5] Carpaneto, Management Sci. 26 pp 736– (1980)
[6] Dantzig, Naval Res. Logistics Quart. 1 pp 217– (1954)
[7] , , , and , TRANSCOL: A multi-period school bus routing and scheduling system. Publication 164, Centre de recherche sur les transports, Montréal (1980).
[8] Desrosiers, RAIRO 17 pp 357– (1983)
[9] , and , Routing and scheduling with time windows solved by network relaxation and branch-and-bound on time variables. In Computer Scheduling of Public Transport, Vol. II. Ed., North-Holland, Amsterdam, in press.
[10] Fisher, Networks 11 pp 109– (1981)
[11] Gertsbakh, Operations Res. 26 pp 68– (1978)
[12] Levin, Transportation Sci. 5 pp 232– (1971)
[13] Magnanti, Networks 11 pp 179– (1981)
[14] Miller, J. Assoc. Comput. Machinery 7 pp 326– (1960) · Zbl 0100.15101 · doi:10.1145/321043.321046
[15] Orloff, Transportation Sci. 10 pp 149– (1976)
[16] Vehicle routing and scheduling with time window constraints: Models and algorithms. Working paper 83-02-01, the Wharton School, University of Pennsylvania (1983).
[17] and , Locomotive maintenance scheduling and train assignment. Publication 239, Centre de recherche sur les Transports, Montréal (1983).
[18] , and , Optimal urban bus routing with scheduling flexibilities. Proceedings of the 11th IFIP Conference on System Modelling and Optimization, P. Thoft-Christensen, Ed., in press.
[19] Soumis, Transportation Res. B 14 pp 181– (1980)
[20] and , Scheduling school buses. Presented at TIMS/ORSA Conference, San Diego (1982). Published by Yale School of Organization and Management, New Haven, CT.
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.