VRP节约里程 java 节约里程法模型构建

倡导节约用水，鼓励邻里节约用水 #生活乐趣# #日常生活乐趣# #环保生活实践# #社区环保活动#

我整理了一些关于软考的项目学习资料+视频（附讲解～～）和大家一起分享、学习一下：

https://d.51cto.com/bLN8S1

节约里程法简介

节约里程法，又称C-W算法 、节约算法或节约法，是由Clarke和Wright于1964年首次提出的，用来解决VRP问题，是重要的物流算法，是用来解决运输车辆数目不确定的问题的最有名的启发式算法。

节约里程法核心思想是依次将运输问题中的两个回路合并为一个回路，每次使合并后的总运输距离减小的幅度最大，直到达到一辆车的装载限制时，再进行下一辆车的优化。优化过程分为并行方式和串行方式两种。

利用节约法确定配送路线的主要出发点是，根据配送中心的运输能力和配送中心到各个用户以及各个用户之间的距离来制定使总的车辆运输的吨公里数最小的配送方案。另还需满足以下条件；（1）所有用户的要求；（2）不使任何一辆车超载；（3）每辆车每天的总运行时间或行驶里程不超过规定的上限；（4）用户到货时间要求。

基本原理

基本思想为为达到高效率的配送，使配送的时间最小距离最短成本最低，而寻找的最佳配送路线。

假定有n个访问地，把每个访问地看成一个点，并取其中的一个点为基点（起点），例如以1点为基点。首先将每个点与该基点相连接，构成线路1→j→1（j=2,3,…,n），这样就得到了一个具有n-1条线路的图（当然，这时尚未形成Hamilton回路）。旅行者按此线路访问这n个点所走的路程总和为

其中为由点1到点j的路段长度，注意此处假定（对所有j）。

若连接点i和点j，即使旅行者走弧（i,j）时（当然这时就不再经过弧（i,1）和弧（1，j），所引起的路程节约值s(i,j)可计算如下

对不同的点对(i,j)，s(i,j)越大，旅行者通过弧(i,j)时所节约的路程越多，因而应优先将其安排到旅行线路中去，使旅行者旅行时通过这一条弧。

迭代步骤

在具体应用该方法时，可按以下步骤进行。

（1）选取基点，例如以1点为基点。将每个点与该基点相连接，得到n-1条线路1→j→1（j=2,3,…,n）。
（2）对不违背限制条件的所有可连接点对(i,j)，如下计算其节约值（i,j不为基点）

（3）将所有按其值的大小由大到小排列。
（4）按的上述顺序，逐个考察其端点i和j，若满足以下条件，就将弧（i,j）插入到线路中。其条件是：
a. 点i和点j不在一条线路上；
b. 点i和点j均与基点相邻。
（5）返回步骤（4），直至考察完所有可插入弧（i,j）为止。
通过以上各迭代步骤，使问题的解逐步得到改善，最后达到满意解（也有可能达到最优解）。

例题

已知配送中心P0向5个用户Pj配送货物，其配送路线网络、配送中心与用户的距离以及用户之间的距离如下图所示，配送中心有3台2t卡车和2台4t两种车辆可供使用。利用节约里程法制定最优的配送方案。

VRP节约里程 java 节约里程法模型构建_VRP节约里程 java_08