Routing with time windows by column generation.

*(English)*Zbl 0571.90088Consider 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.

##### MSC:

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 |

##### Keywords:

m-traveling salesman; column generation; set partitioning; simplex; branch-and-bound; shortest path algorithm; time windows; school bus transportation problems
Full Text:
DOI

**OpenURL**

##### References:

[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 |

[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. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.