Groupe d’études et de recherche en analyse des décisions

G-2021-04

Compact routes for parcel delivery by postal services

, et

In this paper, we introduce a new variant of the vehicle routing problem with time windows (VRPTW) that arises in parcel delivery by postal services. In addition to the standard VRPTW constraints and postal setting characteristics (low time window density and route duration constraints), the problem considered involves route compactness preferences and is called the VRPTW with route compactness (Comp-VRPTW). We measure the compactness of a route as the area of the convex hull of its visited customer locations and, to speed up its computation, we propose two approximate measures: the first frames the route in a rectangle, which can rotate; the second computes the area of a circle whose diameter is determined by the farthest pair of points in the route. This second approach also enables dealing with traveled time instead of geographical distance, which may be more relevant when the distances in the actual road network are far from being Euclidean (due to, e.g., highways, river crossings, or one-way streets). To solve the Comp-VRPTW, we adapt an existing branch-and-price-based large neighborhood search (LNS) heuristic initially designed for the VRPTW. To evaluate the tradeoff between route compactness and the total travel cost, we report computational results obtained on academic Comp-VRPTW instances and on instances derived from a real one provided by our industrial partner. These results show that the proposed measures can greatly improve route compactness at the expense of an increase of the LNS heuristic computational times and of the travel costs for the academic instances that are highly time-constrained.

, 26 pages