车辆路径问题分类，车辆路径分析
背景车辆路线问题(VRP) 是一个组合优化和整数规划问题，它解决“车队向给定客户组交付货物的最佳路线集是什么？”（Masu）。
显示车辆路线问题的照片
这是著名的旅行商问题（TSP）的总结。它首次出现在George Dantzig 和John Ramser 1959 年的一篇论文中。
1959 年George Dantzig 和John Ramser 发表的论文
本文首先创建一种算法并将其应用于汽油输送。
这个问题的背景通常是向从中央仓库订购商品的客户交付商品。
VRP 的目标是最小化总路由成本。
1964 年，Clarke 和Wright 使用称为储蓄算法的高效贪婪方法改进了Dantzig 和Ramser 的方法。
使用PuLP 包使用线性规划来解决此问题，以获得最佳解决方案。
PuLP 是一个用于建模和解决线性规划问题的Python 库。
该数据集总共包含三个CSV 文本文件。
24个首都经纬度位置.csv
距离distance.csv
飞行时间flight_time.csv
您可以将执行结果设置给变量K来表示销售人员的数量。请注意，如果K 大于4，则可能需要几个小时。
K=1人（所用时间： 7.3秒）• 总停留时间： 6494（分钟）• 总距离： 12287.07（公里）K=1
K=2 人（耗时： 2.7 秒） 总耗时： 3574（分钟） 总距离： 12607.64（公里） K=2
K=3人（所需时间： 4分4秒） 总停留时间： 2546（分钟） 总距离： 14130.25（公里） K=3
K=4人（所需时间： 28分32秒） 总停留时间： 1988（分钟） 总距离： 15425.02（公里） K=4
完整源代码导入包frompulp import *import numpy as npimport pandas as pdimport matplotlib.pyplot as plt%matplotlib inlineimport seaborn as sn# 部分网站=['巴塞罗那','贝尔格莱德','柏林','布鲁塞尔' , '布加勒斯特', '布达佩斯', '哥本哈根', '都柏林', '汉堡', '伊斯坦布尔', '基辅', '伦敦', '马德里', '米兰', '莫斯科', '慕尼黑', '巴黎'', '布拉格', '罗马', '圣彼得堡', '索非亚', '斯德哥尔摩', '维也纳', '华沙']latlng=['纬度', '经度']position=pd.read_csv ('./data/position.csv',index_col='城市')flighttime=pd.read_csv('./data/flight_time.csv',index_col='城市') 距离=pd.read_csv('./data/distance.csv ',index_col='City')position.head(5)#创建一些位置（这样你就可以画这个）position=dict( ( city, (position.loc[city , 'longitude'],position.loc [city, 'latitude']) ) for city in site) for s atposition : p=position[s] plt.plot(p[0],p[1] ,'o') plt.text(p[0] ]+.01 ,p[1],s,horizontalalignment='left',verticalalignment='center') plt.gca().axis('off' ); 欧洲首都
#获取城市之间的距离distances=dict( ((s1,s2), distance.loc[s1, s2] ) for s1 in Positions for s2 in Position if s1!=s2) Modeling K=2 #销售会员数量#initialization Problem prob=Lp Problem('vehicle', LpMinimize) #若站点i与游览站点j相连，指示变量x=LpVariable.dicts('x', distances, 0, 1,LpBinary)#删除虚拟变量子路径u=LpVariable.dicts('u', sites, 0, len(sites)-1, LpInteger)#目标成本=lpSum([x[(i,j)]* 距离[(i,j)] for ( i,j ) in distances])prob+=cost# 对site: 中k 的约束cap=1 if k !='Berlin' else K #入站连接prob+=lpSum([ x[ (i,k)] for i in site if (i, k) in x])==cap #出站连接概率b+=lpSum([ x[(k,i)] for i inites if (k,i) in x])==cap N=len(sites )/Kfor i in site: for j in site: if i !=j and (i !='Berlin' and j!='Berlin') and (i,j) in x: prob +=u[i] - u[j ]=(N)*(1-x[(i,j)]) - 1solve%time prob.solve()print(LpStatus[prob.status])non_zero_edges=[ e for e in x if value(x[e ]) !=0 ]def get_next_site(parent):edges=[e for e in non_zero_edges if e[0]==parent] for e inedges: non_zero_edges.remove(e) return Edge Tours=get_next_site( '柏林')tours=[ [e ] for e in Tours ]for t in Tours: while t[-1][1] !='Berlin': t.append(get_next_site(t[-1] [1])[ -1]) t 的最优路线tour : print(' - '.join([ a for a,b in t]+['柏林'])) 柏林- 哥本哈根- 斯德哥尔摩- 圣彼得堡- 莫斯科- 基辅- 布加勒斯特- 伊斯坦布尔- 索非亚- 贝尔格莱德- 布达佩斯- 维也纳- 华沙- 柏林柏林- 布拉格- 慕尼黑- 米兰- 罗马- 巴塞罗那- 马德里- 都柏林- 伦敦- 巴黎- 布鲁塞尔- 汉堡- 柏林计算总时间。
TotalTime=0;t 游览时间：=0 range(0, len(t)): i time +=Flighttime.loc[t[i][0], t[i][1]] if time totalTime: TotalTime=时间打印（总时间）3574
#绘制路线color=[np.random.rand(3) for i in range(len(tours))]for t,c in zip(tours,colors): for a,b in t: p1,p2=Positions[ a ], Positions[b] plt.plot([p1[0],p2[0]],[p1[1],p2[1]], color=c)#在位置： 处再次绘制s 的地图p=位置[ s] plt.plot(p[0],p[1],'o') plt.text(p[0]+.01,p[1],s,horizontalalignment='left',verticalalignment=' center' ) plt.title('%d '%K + '个人' if K 1 else '1 人')plt.xlabel('纬度')plt.ylabel('经度')plt.rcParams['font.sans -serif']=['SimSun']# plt.gca().axis('off')plt.show()K=2
print('总花费时间：',totalTime, '(min)')print('总距离：', value(prob.objective), '(km)') 总花费时间： 3574 (min) 总距离： 12607.64 (km) 总结随着K（销售人员数量）的增加，最好不要使用线性规划来解决问题。应使用元启发式算法方法。您的解决方案可能不是最佳的，但速度要快得多。
