Mancini Simona, Gansterer Margaretha
Department of Engineering, University of Palermo, Viale delle Scienze 8, Palermo, 90128 Italy.
Department of Operations, Energy, and Environmental Management, University of Klagenfurt, Universitaetstrasse 65-67, 9020 Klagenfurt, Austria.
Flex Serv Manuf J. 2024;36(4):1189-1221. doi: 10.1007/s10696-023-09529-3. Epub 2024 Jan 9.
In this paper, we address the vehicle routing problem (VRP) with occasional drivers (ODs) and time windows (TWs). The problem (VRP-OD-TW) is an extension of the VRP-OD, where ODs serve customers within given TWs. Differently from the basic version of VRP-OD-TW, we assume that ODs not only accept single requests, but they can also serve bundles of requests. To deal with the bundle-to-driver assignment problem, an auction-based system has been designed; a company offers a set of bundles to the ODs, who bid for all the bundles they consider attractive. There is no limit on the number of bids a driver can place, but at most one bid per OD can be assigned to avoid infeasible workloads. This system could yield a large cost reduction for the company, but its success is strongly related to the bundles offered. Hence, determining bundles which are attractive for ODs and profitable for the company, becomes a crucial issue. We propose two different bundling strategies, which make use of a spatial-temporal representation of customers in a three-dimensional (3D) space. The former is based on the generation of 3D corridors, while the latter relies on 3D clustering techniques. Through extensive computational results, we show that the former technique outperforms the latter in terms of both solution quality and computational times and that both the approaches strongly outperform bundle generation techniques that neglect the temporal dimension and rely only on spatial information.
在本文中，我们研究了带临时司机（OD）和时间窗（TW）的车辆路径问题（VRP）。该问题（VRP-OD-TW）是VRP-OD的扩展，其中临时司机在给定的时间窗内为客户提供服务。与VRP-OD-TW的基本版本不同，我们假设临时司机不仅接受单个请求，还可以处理请求束。为了解决请求束与司机的分配问题，设计了一个基于拍卖的系统；一家公司向临时司机提供一组请求束，临时司机对他们认为有吸引力的所有请求束进行投标。司机可以投标的数量没有限制，但每个临时司机最多只能分配一个投标，以避免产生不可行的工作量。该系统可以为公司大幅降低成本，但其成功与提供的请求束密切相关。因此，确定对临时司机有吸引力且对公司有利可图的请求束成为一个关键问题。我们提出了两种不同的捆绑策略，它们利用了客户在三维（3D）空间中的时空表示。前者基于3D走廊的生成，而后者依赖于3D聚类技术。通过广泛的计算结果，我们表明，在解决方案质量和计算时间方面，前一种技术优于后一种技术，并且这两种方法都明显优于忽略时间维度且仅依赖空间信息的请求束生成技术。
