节约里程算法的python实现
说明：节约里程法(Saving Algorithm)又称节约算法，是指用来解决运输车辆数目不确定的VRP问题的最有名的启发式算法。是由Clarke和Wright于1964年首次提出的。
背景
为什么写这个程序，因为我在做课设的时候算的过程太复杂了，一个数据出错要重算，当时就想做一个程序出来，但是因为课设只有一周的时间，所以只能作罢。附上我课设论文。虽然它只有74分o(╥﹏╥)o
https://github.com/ishelo/VRP-CW/blob/master/扫描算法介绍及题目.pdf
环境
windows 10 企业版LTSC
python 3.7.2
项目地址
https://github.com/ishelo/VRP-CW
项目核心代码
def savingsAlgorithms(self):
saving = 0
for i in range(1, len(self.q)):
self.Routes.append([i])
for i in range(1, len(self.Routes) + 1): # 使用Sij = Ci0 + C0j - Cij计算节约度
for j in range(1, len(self.Routes) + 1):
if i == j:
pass
else:
saving = (self.distance[i][0] + self.distance[0][j]) - self.distance[i][j]
self.savings.append([i, j, saving]) # 将结果以元组形式存放在列表中
self.savings = sorted(self.savings, key=itemgetter(2), reverse=True) # 按照节约度从大到小进行排序
for i in range(len(self.savings)):
print(self.savings[i][0],'--',self.savings[i][1], " ",self.savings[i][2]) # 打印节约度
for i in range(len(self.savings)):
startRoute = []
endRoute = []
routeDemand = 0
for j in range(len(self.Routes)):
if (self.savings[i][0] == self.Routes[j][-1]):
endRoute = self.Routes[j]
elif (self.savings[i][1] == self.Routes[j][0]):
startRoute = self.Routes[j]
if ((len(startRoute) != 0) and (len(endRoute) != 0)):
for k in range(len(startRoute)):
routeDemand += self.q[startRoute[k]]
for k in range(len(endRoute)):
routeDemand += self.q[endRoute[k]]
routeDistance = 0
routestore = [0]+endRoute+startRoute+[0]
for i in range(len(routestore)-1):
# print(routestore[i],routestore[i+1])
# print(self.distance[routestore[i]][routestore[i+1]])
routeDistance += self.distance[routestore[i]][routestore[i+1]]
#print(routestore,"== ==:",routeDistance)
if (routeDemand <= self.tons) and (routeDistance <= self.distanceLimit): # 按照限制规则对路线进行更改
self.Routes.remove(startRoute)
self.Routes.remove(endRoute)
self.Routes.append(endRoute + startRoute)
break
for i in range(len(self.Routes)):
self.Routes[i].insert(0, 0)
self.Routes[i].insert(len(self.Routes[i]), 0)
# -----------输出最终结果---------------------
def printRoutes(self):
for i in self.Routes:
costs = 0
for j in range(len(i)-1):
costs += self.distance[i[j]][i[j+1]]
print("路线: ",i," 路程: ",costs)
食用方法
确保电脑上安装了python3，将各点距离输入到.csv文件中，修改vrp.py中的参数，并运行main.py
输出结果
以课设数据为例，输出结果。
结语
节约里程法作为解决物流VRP中重要的启发式算法，身为一个物流人，尤其是物流管理专业的学生，是必须掌握的。
节约算法根据配送中心的运输能力和配送中心到各个用户以及各个用户之间的距离来制定使总的车辆运输的吨公里数最小的配送方案。它依次将运输问题中的两个回路合并为一个回路，每次使合并后的总运输距离减小的幅度最大，直到达到一辆车的装载限制时，再进行下一辆车的优化。
节约里程算法的python实现，解决了其复杂的计算过程，虽然还有些不足之处，以后可以再继续改进。