Reverse multistar inequalities and vehicle routing problems with a lower bound on the number of customers per route
Reverse multistar inequalities and vehicle routing problems with a lower bound on the number of customers per route
复制标题
通过每条路线的客户数量下限来逆转多星不平等和车辆路线问题
作者：
L. Gouveia;Jorge Riera;Juan José SALAZAR
本文分析了一个车辆路径问题的单商品流模型的流变量投影得到的不等式。这些不等式被称为逆多星(RMS)不等式，它们与其他文章中分析和使用的MS不等式有关。虽然均方根不等式对于某些车辆路径问题并不重要，但在另一些车辆路径问题中，它们是基本的。本文提出了一个RMS感兴趣的车辆路径问题。这就是具有上下限能力的车辆路径问题(LU-VRP)。它涉及一个车辆段和一个同质车队的车辆路径问题。所有的客户都有一个单位需求，每辆车的需求都有上下限。通过加强均方根不等式得到了新的不等式族。计算实验表明，新的不等式在求解LU-VRP实例时是有用的。这些实验基于对称和非对称VRP库(VRPLIB)实例的变体，最多有100个客户。在车辆数量固定的单位需求有能力车辆路径问题中，隐含着对每条路线上服务的最小顾客数量的约束。因此，文章还评估了在这一变式的背景下使用下限不等式的影响。新的不平等能否帮助解决这个问题仍是个未知数。我们的理论分析表明，一族已发展的不等式族并不包含在其他标准的不等式族中。这促使我们继续研究，寻找这种变体的其他基于下界的不等式族。©2012 Wiley期刊，Inc.网络，2013
This article analyzes inequalities derived by projecting out the flow variables of a single‐commodity flow model for a vehicle routing problem. These inequalities are called reverse multistar (RMS) inequalities and are related to the MS inequalities analyzed and used in other articles. Although the MS RMS inequalities are irrelevant for some vehicle routing problems, in others they are fundamental. The article presents a vehicle routing problem in which the RMS are of interest. It is called the vehicle routing problem with lower and upper bound capacities (LU‐VRP). It concerns a vehicle routing problem with one depot and a homogeneous fleet of vehicles. All the customers have a unit demand, and there are upper and lower bounds on the demand covered by each vehicle. New families of inequalities are derived by strengthening the RMS inequalities. Computational experiments show that the new inequalities are useful when solving LU‐VRP instances. The experiments are based on variations of symmetric and asymmetric VRP library (VRPLIB) instances with up to 100 customers. The constraint on a minimum number of customers served in each route is implicit in the unit‐demand capacitated vehicle routing problem with a fixed number of vehicles. Therefore, the article also evaluates the impact of using the lower bound inequalities developed in the context of this variant. It is still unknown whether the new inequalities can help solve it or not. Our theoretical analysis suggests that one of the families of developed inequalities is not implied by other standard inequalities. This prompts us to pursue studies in the search for other families of lower bound based inequalities for this variant. © 2012 Wiley Periodicals, Inc. NETWORKS, 2013
多仓库销售员负载平衡问题的公式和 Benders 分解算法
影响因子：
6.4
作者：
Bektas T
通讯作者：
Bektas T