考虑一致性约束的车辆路径问题综述

A Survey of the Consistent Vehicle Routing Problem

车辆路径问题是物流和交通运输领域的研究热点。近年来,为应对激烈的市场竞争,越来越多的企业开始关注如何在降低成本的同时保证服务效率和服务质量。实践表明提高车辆路径方案的一致性不仅可以提高服务效率,还能显著提高客户满意度。因此,考虑一致性约束的车辆路径问题(又称一致性车辆路径问题)应运而生。一致性车辆路径问题是相对较新的车辆路径问题变种,相关成果具有重要的实践和学术价值。随着多样化一致性约束的提出以及相关数学模型和优化方法的迭代更新,目前针对一致性车辆路径问题已有一定数量的研究积累。本文从车辆路径问题的分类、一致性车辆路径问题的背景介绍、模型、求解算法等方面对该问题进行了综述。在一致性车辆路径问题中,一致性约束主要有时间一致性、人员一致性和路线一致性要求。时间一致性和人员一致性约束较为常见,路线一致性约束则相对更为新颖。一致性车辆路径问题的求解方法以启发式算法为主,尤其是大、中型实例(时间周期5d,客户数量50以上)的求解;而部分精确式算法对中小型实例(时间周期3~5d,客户数量50及以下)也展现了良好的性能。

The vehicle routing problem(VRP)is a major research topic in the field of logistics and transportation.In recent years,to cope with the fierce market competition,increasingly more enterprises have begun to focus on how to reduce costs while ensuring service efficiency and service quality.Practice shows that improving the consistency of vehicle routing solutions can not only improve service efficiency but also significantly enhance customer satisfaction.Therefore,the VRP considering consistency constraints(also known as the consistent VRP(ConVRP))has emerged.The ConVRP is a relatively new variant of the VRP,and the related research results have important practical and academic value.With the consideration of diverse consistency constraints and the development of related mathematical models and solution methods,a considerable amount of research has been accumulated on the ConVRP.This study summarizes the classification,background,models and algorithms of the ConVRP.Consistent constraints mainly include time consistency,driver consistency,and route consistency.Time consistency and driver consistency constraints are common,whereas route consistency constraints are more novel.ConVRP methods are usually based on heuristic algorithms,especially for large and medium-sized instances(with time periods of 5 days and>50 customers).For small and medium-sized instances(with time periods of 3~5 days and<50 customers),some exact algorithms also exhibit good performance.