The Split Delivery Vehicle Routing Problem with Time Windows and Customer Inconvenience Constraints
The Split Delivery Vehicle Routing Problem with Time Windows and Customer Inconvenience Constraints
复制标题
DOI：
10.1287/trsc.2018.0862
复制
发表时间：
2019-05
期刊：
影响因子：
--
通讯作者：
Nicola Bianchessi;Michael Drexl;Stefan Irnich
中科院分区：
文献类型：
--
作者：
Nicola Bianchessi;Michael Drexl;Stefan Irnich
在经典的路由问题中，每个客户只被访问一次。相比之下，当允许分批送货时，客户可能会通过多次访问获得服务。这可能会大大节省差旅费用。即使分批送货对运输公司是有利的，客户方面也可能不希望进行多次访问：每次访问时，客户都必须中断其主要活动并处理货物收据。本论文的贡献在于透彻地分析了分批交付分配策略的可能性和局限性。为此，我们调查了两种不同类型的限制客户不便的措施(最大访问次数和交付的时间同步)，并通过不同的目标函数(包括可变路径成本、与路径持续时间相关的成本、XED成本)来评估这些措施对运营商效率的影响。我们考虑了允许分批发货的带时间窗的车辆路径问题(SDVRPTW)，并给出了考虑顾客不便约束的相应推广(SDVRPTW-IC)。我们设计了一种扩展的分枝切割算法来求解SDVRPTW-IC，并报告了实验结果，显示了客户不便约束的影响。最后，在实验分析的基础上，为物流管理者提供了有益的启示。
In classical routing problems, each customer is visited exactly once. By contrast, when allowing split deliveries, customers may be served through multiple visits. This potentially results in substantial savings in travel costs. Even if split deliveries are bene?cial to the transport company, several visits may be undesirable on the customer side: at each visit the customer has to interrupt his primary activities and handle the goods receipt. The contribution of the present paper consists in a thorough analysis of the possibilities and limitations of split delivery distribution strategies. To this end, we investigate two different types of measures for limiting customer inconvenience (a maximum number of visits and the temporal synchronization of deliveries) and evaluate the impact of these measures on carrier e?ciency by means of different objective functions (comprising variable routing costs, costs related to route durations, ?xed ?eet costs). We consider the vehicle routing problem with time windows in which split deliveries are allowed (SDVRPTW) and de?ne the corresponding generalization that takes into account customer inconvenience constraints (SDVRPTW-IC). We design an extended branch-and-cut algorithm to solve the SDVRPTW-IC and report on experimental results showing the impact of customer inconvenience constraints. We ?nally draw useful insights for logistics managers on the basis of the experimental analysis carried out.