Solomon, Marius M.; Baker, Edward K.; Schaffer, Joanne R. Vehicle routing and scheduling problems with time window constraints: Efficient implementations of solution improvement procedures. (English) Zbl 0642.90054 Vehicle routing: Methods and studies, Stud. Manage. Sci. Syst. 16, 85-105 (1988). Summary: [For the entire collection see Zbl 0638.00043.] A number of heuristic algorithms have been proposed for the vehicle routing and scheduling problem with time window constraints. These algorithms include both route construction and route improvement procedures. This paper extends branch exchange solution improvement procedures, well known from the standard vehicle routing literature, to vehicle routing and scheduling problems with time window constraints. We focus on efficient implementations of these procedures and present extensive computational results. The methods presented are completely robust in that significant reductions in running time are achieved without any degradation in the quality of the solution. Cited in 11 Documents MSC: 90B35 Deterministic scheduling theory in operations research 90C27 Combinatorial optimization 65K05 Numerical mathematical programming methods Keywords:heuristic algorithms; vehicle routing; time window constraints; branch exchange solution improvement Citations:Zbl 0638.00043 PDFBibTeX XML