A robust optimization approach for the capacitated vehicle routing problem with demand uncertainty
A robust optimization approach for the capacitated vehicle routing problem with demand uncertainty
复制标题
DOI：
10.1080/07408170701745378
复制
发表时间：
2008-03
期刊：
影响因子：
--
通讯作者：
I. Sungur;F. Ordóñez;M. Dessouky
中科院分区：
文献类型：
--
作者：
I. Sungur;F. Ordóñez;M. Dessouky
本文提出了一种求解需求不确定车辆路径问题的稳健优化方法。这种方法产生的路线使运输成本最小化，同时满足给定的有界不确定性集合中的所有需求。我们证明了对于VRP和特定不确定性集的Miller-Tucker-Zemlin公式，求解稳健解并不比求解单个确定性VRP更困难。我们在基准实例和集群实例族上的计算结果表明，健壮的解决方案可以防止未满足的需求，同时在确定性最优路径上产生少量的额外成本。对于中等不确定性的集群实例，这一点最为明显，其中剩余的车辆容量用于防止每个集群内的变化，额外成本很小。我们将稳健优化模型与经典的随机VRP模型进行了比较，以说明它们之间的异同。我们还观察到，稳健的解决方案相当于对剩余车辆容量的巧妙管理，而不是将这些闲置空间均匀和非均匀地分配给车辆。
In this paper we introduce a robust optimization approach to solve the Vehicle Routing Problem (VRP) with demand uncertainty. This approach yields routes that minimize transportation costs while satisfying all demands in a given bounded uncertainty set. We show that for the Miller–Tucker–Zemlin formulation of the VRP and specific uncertainty sets, solving for the robust solution is no more difficult than solving a single deterministic VRP. Our computational results on benchmark instances and on families of clustered instances show that the robust solution can protect from unmet demand while incurring a small additional cost over deterministic optimal routes. This is most pronounced for clustered instances under moderate uncertainty, where remaining vehicle capacity is used to protect against variations within each cluster at a small additional cost. We compare the robust optimization model with classic stochastic VRP models for this problem to illustrate the differences and similarities between them. We also observe that the robust solution amounts to a clever management of the remaining vehicle capacity compared to uniformly and non-uniformly distributing this slack over the vehicles.