A column generation based heuristic for the generalized vehicle routing problem with time windows. (August 2021)

• Record Type: Journal Article
• Authors: Yuan, Yuan; Cattaruzza, Diego; Ogier, Maxime; Semet, Frédéric; Vigo, Daniele
• Is Part Of: Transportation research. Volume 152(2021)
• Publication Date: 2021-08
• Subjects: Generalized vehicle routing problem -- Time windows -- Last mile delivery -- Delivery options -- Trunk/in-car delivery; Logistics -- Periodicals; Transportation -- Periodicals; 388.011
• DOI: 10.1016/j.tre.2021.102391
• Languages: English
• ISSNs: 1366-5545

Abstract

Highlights: Studied the generalized vehicle routing problem with time windows (GVRPTW). Proposed a column generation based heuristic for the GVRPTW. Several types of benchmark instances can be solved efficiently and effectively. Abstract: The generalized vehicle routing problem with time windows (GVRPTW) is defined on a directed graph G = ( V, A ) where the vertex set V is partitioned into clusters. One cluster contains only the depot, where is located a homogeneous fleet of vehicles, each with a limited capacity. The other clusters represent customers. A demand is associated with each cluster. Inside a cluster, the vertices represent the possible locations of the customer. A time window is associated with each vertex, during which the visit must take place if the vertex is visited. The objective is to find a set of routes such that the total traveling cost is minimized, exactly one vertex per cluster is visited, and all the capacity and time constraints are respected. This paper presents a set covering formulation for the GVRPTW which is used to provide a column generation based heuristic to solve it. The proposed solving method combines several components including a construction heuristic, a route optimization procedure, local search operators and the generation of negative reduced cost routes. Experimental results on benchmark instances show that the proposed algorithm is efficient and high-quality solutions for instances with up to 120 clusters are obtained within short computation times.