A synthesis of assignment and heuristic solutions for vehicle routing with time windows

A synthesis of assignment and heuristic solutions for vehicle routing with time windows

0.00 Avg rating0 Votes
Article ID: iaor20042643
Country: United Kingdom
Volume: 55
Issue: 1
Start Page Number: 2
End Page Number: 11
Publication Date: Jan 2004
Journal: Journal of the Operational Research Society
Authors: ,
Abstract:

This paper proposes a three-stage method for the vehicle-routing problem with time window constraints (VRPTW). Using the Hungarian method the optimal customer matching for an assignment approximation of the VRPTW, which is a travel time-based relaxation that partially respects the time windows, is obtained. The assignment matching is transformed into feasible routes of the VRPTW via a simple decoupling heuristic. The best of these routes, in terms of travelling and vehicle waiting times, form part of the final solution, which is completed by the routes provided by heuristic methods applied to the remainder of the customers. The proposed approach is tested on a set of standard literature problems, and improves the results of the heuristic methods with respect to total travel time. Furthermore, it provides useful insights into the effect of employing optimal travel time solutions resulting from the assignment relaxation to derive partial route sets of the VRPTW.

Reviews

Required fields are marked *. Your email address will not be published.