下载掌阅APP，畅读海量书库
立即打开
路径优化问题是组合优化中的一类经典问题，它的主要应用领域为交通运输和物流。但在其他很多领域中也有相应的应用。除了在物流领域中的应用，路径优化问题也在服务行业中有较为广泛的应用。在这个情境中，车辆是一个更为抽象的概念，指代通过访问不同的地点来完成指定任务的活动。因此，从更一般的意义上来讲，路径优化问题包括所有可以用图来表示的活动，其结果是通过访问不同的边或点组成一个或多个环。
路径优化问题（Vehicle Routing Problem）最早由Danzig和Ramser 于1959年在其论文“The Truck Dispatching Problem”中提出。该问题是组合优化问题中的一个重要研究方向，并且在包括交通、物流、通信、生产和军事等领域都有极为重要的应用。经典的路径优化问题定义如下：在图G=（V，A）中，V={v 0 ，v 1 ，…，v n }代表图中点的集合，A={（v i ，v j ）：v i ，v j ∈V，i≠j}为图中弧的集合。其中，点v 0 表示车场（仓库），剩余的点代表不同的客户。对应弧的集合A我们定义一个成本集合（c ij ）和行驶时间矩阵（t ij ）。通常情况下，成本矩阵和行驶时间矩阵均为对称矩阵。因此，路径优化问题通常用无向图G=（V，E）来定义，其中E={（v i ，v j ）：v i ，v j ∈V，i≠j}为图中边的集合。此外，每位客户的需求为q i （q i ≠0）。服务该客户的时间为t i 。基本问题中通常假设服务车辆为同质车辆，即车队中有m辆完全相同的车辆。载重限制为Q，服务车辆每天从车场出发开始每一天的工作，并于工作结束后返回车场。
经典路径优化问题一般需要满足以下约束条件：①每条路线从车场开始和结束；②每个客户每天由且仅由一辆车提供一次服务；③每条路线服务客户的总需求不超过载重限制Q；④每条路线的总时间不超过工作时长限制D。目标函数为最小化总成本，包括行驶时间成本和服务时间成本。