Methods for bi-objective routing and districting problems

doi:10.1111/itor.70050

2025-05-19

PRE

Margarida Aires de Abreu *

Daniel Santos *

José Rui Figueira *

DOI：10.1111/itor.70050

原文链接

原文求助

摘要

En 中文

分区和路径规划是优化运输系统及复杂物流运作的关键组成部分。将这些组成部分相结合，有助于企业高效地向全球交付货物，降低成本并提升服务水平。本研究为该领域做出贡献，提出了一种精确求解方法，以解决涉及分区和路径规划决策的双目标问题。所解决的问题包括将一组客户划分为分区，并确定满足其需求的路线。该问题被称为容量约束车辆路径与分区问题（CVRDP），它结合了容量约束车辆路径问题（CVRP）与分区问题。每个分区有一条路线，且每条路线均从单一配送中心出发并返回，恰好一次访问该分区的所有客户。车辆在满足客户需求的同时需遵守容量约束。该双目标问题旨在最小化总旅行时间和分区的离散度。提出了四种混合整数线性规划模型，它们在防止子回路的方法上有所不同。这些模型包括改进的Miller-Tucker-Zemlin（MTZ）和单商品流（SCF）模型，并包含其分解和聚合版本。研究采用增广epsilon$\epsilon$-约束方法来寻找，通常称为，帕累托前沿。在计算实验中，使用来自文献的改编实例进行四阶段分析，其中分区数量预先确定。总体而言，分解型SCF模型表现优于其他模型。该模型也是优化单目标问题的最佳选择，特别是在实现紧凑分区和最小化总旅行时间方面。

Keyword:

bi-objective problem

capacitated vehicle routing problem

districting problem

epsilon-constraint

compactness

dispersion