用Python计算合肥地铁乘车最优乘车路线：暴力方式

假设地铁平均速度60km/h,平均换乘耗时5分钟，列车各站停留时间30秒。已知乘车站及下车站，求最优乘车路线。

也就是最少换乘路线与最短路径之间的选择

首先需要准备的数据：

1.合肥1-3号线站点信息，

根据站名获取纬度，进而获取站点距离

2，构建紧邻图graph。（可以向高德索取数据并整理）

def get_location(keyword,city):#获得经纬度keyword = keyword+"(地铁站)"user_agent='Mozilla/5.0 (Macintosh; U; Intel Mac OS X 10_6_8; en-us) AppleWebKit/534.50 (KHTML, like Gecko) Version/5.1 Safari/534.50'headers = {'User-Agent': user_agent}url='http://restapi.amap.com/v3/place/text?key='+keynum+'&keywords='+keyword+'&types=&city='+city+'&children=1&offset=1&page=1&extensions=all'data = requests.get(url, headers=headers)data.encoding='utf-8'data=json.loads(data.text)result=data['pois'][0]['location'].split(',')return result[0],result[1]def compute_distance(longitude1,latitude1,longitude2,latitude2):#计算两个地铁站的距离user_agent='Mozilla/5.0 (Macintosh; U; Intel Mac OS X 10_6_8; en-us) AppleWebKit/534.50 (KHTML, like Gecko) Version/5.1 Safari/534.50'headers = {'User-Agent': user_agent}#url='http://restapi.amap.com/v3/distance?key='+keynum+'&origins='+str(longitude1)+','+str(latitude1)+'&destination='+str(longitude2)+','+str(latitude2)+'&type=3'两点距离url = 'http://restapi.amap.com/v3/direction/transit/integrated?key='+keynum+'&origin='+str(longitude1)+','+str(latitude1)+'&destination='+str(longitude2)+','+str(latitude2)+'&city=合肥&cityd=合肥&strategy=0&nightflag=0&date=2014-3-19&time=22:34'data=requests.get(url,headers=headers)data.encoding='utf-8'data=json.loads(data.text)result=data['route']['distance']return resultdef get_graph():print('正在创建pickle文件...')data=pd.read_excel('./subway.xlsx')#创建点之间的距离graph=defaultdict(dict)for i in range(data.shape[0]):site1=data.iloc[i]['line']if i<data.shape[0]-1:#print(site2)site2=data.iloc[i+1]['line']#如果是共一条线if site1==site2:longitude1,latitude1=data.iloc[i]['longitude'],data.iloc[i]['latitude']longitude2,latitude2=data.iloc[i+1]['longitude'],data.iloc[i+1]['latitude']name1=data.iloc[i]['name']name2=data.iloc[i+1]['name']distance=compute_distance(longitude1,latitude1,longitude2,latitude2)graph[name1][name2]={'line':site1,'distance':distance}graph[name2][name1]={'line':site1,'distance':distance}output=open('graph.pkl','wb')pickle.dump(graph,output)

暴力的解决问题：

1，遍历出所有路径,以及换乘次数，换乘线路，路径距离

2，找到最短路径（也可能是最短距离），和最少换乘路径进行比较

import pickledef find_allPath(graph,start,end,path=[]):path = path +[start]if start == end:return [path]#print(path)paths = [] #存储所有路径    for node in graph[start]:if node not in path:newpaths = find_allPath(graph,node,end,path) for newpath in newpaths:paths.append(newpath)return pathsdef compare_allPath(start,end,path=[]):paths =find_allPath(graph,start,end,path=[])line_num=[]tr_=[]distances=[]for path in paths:line,distance,tr = [],[],[]for i in range(len(path)-1):li=graph[path[i]][path[i+1]]['line']if len(line)==0:line.append(str(li))elif str(li) != line[-1]:line.append(str(li))tr.append(path[i])distance.append(graph[path[i]][path[i+1]]['distance'])line_num.append(line)tr_.append(tr)distances.append(sum([int(d) for d in distance]))tr_num = [len(i) for i in tr_]if distances.index(min(distances)) != tr_num.index(min(tr_num)):#计算最短距离与最少换成的耗时差异#最短路径与最少换乘的距离差距path_dis_diff = distances[distances.index(min(distances))]-distances[tr_num.index(min(tr_num))]#过站数量差异：station_diff = len(path[distances.index(min(distances))])-len(path[tr_num.index(min(tr_num))])#最短路径与最少换乘的换乘距离差距path_tr_num_diff = tr_num[distances.index(min(distances))]-tr_num[tr_num.index(min(tr_num))]#如果距离耗时与换乘时间做比较:假设地铁速度60km/h,换乘耗时5分钟if abs(station_diff)*0.5+abs(path_dis_diff)/1000<path_tr_num_diff*5:path,linen,tr=paths[tr_num.index(min(tr_num))],line_num[tr_num.index(min(tr_num))],tr_[tr_num.index(min(tr_num))]else:path,linen,tr=paths[distances.index(min(distances))],line_num[distances.index(min(distances))],tr_[distances.index(min(distances))]else:path,linen,tr=paths[distances.index(min(distances))],line_num[distances.index(min(distances))],tr_[distances.index(min(distances))]if len(line)>1:print('需要搭乘{}号地铁'.format(','.join(list(linen))))print('换乘站是{}'.format(','.join(tr)))print('路线规划为：','-->'.join(path))else:print('需要搭乘{}号地铁'.format(','.join(list(linen))))print('路线规划为：','-->'.join(path)) return path,linen,trif __name__ == '__main__':global graphfile=open('graph.pkl','rb')graph=pickle.load(file)#compare_allPath('职教城','幸福坝')#compare_allPath('洪岗','包公园')compare_allPath('职教城','幸福坝')

该方法是最LOW的方法，下篇将用dijkstra解决最短路径问题