山东住房和建设庭网站,深圳公司标牌制作,电视剧手机网站大全,台州快速建站公司一、问题描述
城市轨道交通的繁荣发展#xff0c;带来了车辆资源需求的日益增加。如何兼顾运营服务水平和运营成本#xff0c;以最少的车底优质地完成运输任务成为一大严峻问题。本题在后续的描述中将由多辆动车和拖车组合而成的车组称为车底。在日常的运营组织中#xff0…一、问题描述
城市轨道交通的繁荣发展带来了车辆资源需求的日益增加。如何兼顾运营服务水平和运营成本以最少的车底优质地完成运输任务成为一大严峻问题。本题在后续的描述中将由多辆动车和拖车组合而成的车组称为车底。在日常的运营组织中车底运用计划指导着所有的车底有序的完成运输任务是运输计划中非常重要一项。较多的车底运用数可以从容的面对各种客流压力深受乘客的欢迎却往往不能发挥车底的运输能力导致运营成本骤升;而车底过少又极易引起车底超负荷运转缩短设备寿命面对大客流情况还有可能出现运营紊乱乘客体验差。因此车底运用计划对协调运营质量和运营成本意义重大。基于列车运行时刻表结合列车车底数量、车辆段或停车场以下统称为车场的数量、车场的分布状况及容纳能力等对每一车底在何时何地驶出车场、担当哪些车次以及返回车场作出合理的安排同时根据车底检修相关规程对每一车底的检修时间、检修地点、检修级别等作出具体安排保证安全、高效、有序的完成日常运营任务。
现在假设有一个地铁运营线该线网由 20 座车站构成 本线路全周转时间120min30s共有 35 组停车场的存车能力为 25车辆段的存车能力为 20列车运行间隔早高峰 3min7点到9点平峰 8min晚高峰3min25s17点到20点其中大交路 1-20小交路1-15早晚高峰的追踪间隔均指小交路的追踪间隔列车通过 9 号车站进出车辆段出入段时间为 2min40s11520 号车站具备折返能力其最短折返时间分别为6min、4min30s、4min30s1号车 站连接停车场停车场的出入时间 2min。 简而言之要求就是使用最少的车底完成所有车次的牵引计划同时每辆车的牵引时长要尽量均衡。
二、数据介绍
车次数据分位上行车次和下行车次上行车次表示从编号较大的站到编号较小的站下行车次从编号较小的站到编号较大的站流入从1到20是下行车次从20到1是上行车次。每天的上、下行车次数各为244。
三、算法求解
在这一小节中主要介绍两部分内容第一部分内容是如何获得使用车底尽量少的车底牵引方案第二部分是如何在保证车底数量不变的前提下使得每个车底的牵引时间更加均衡。
3.1 车底数量求解
贪心算法 对于此类问题一个直观的想法采用贪心的策略对于每一个车底都使得牵引尽量多的车次直到所有的车次完成牵引这个时候用到的车底数量就是贪心算法得到的最少车底数量基本算法流程如下
step1、初始化使用车底集合为C{}当前车底牵引车次集合D{}剩余车次集合P为上下行全量车次 step2、按照时空接续关系生成所有可行车次集合如果可行车次为空转step4 step3、随机选择可行接续车次作为车底即将牵引的车次d,DDdPP-d转step2 step4 、如果剩余车底集合P为空转step6否则转step5 step5、更新使用车底集合C新增车底转step2 step6、输出车底牵引计划 step7、结束。
其中step2中的时空接续关系是指车底前后牵引的两趟车次在时间和空间上都必须是能够衔接的在空间上前车的终点站必须是后撤的起点站在时间上前车的到达时间必须早于后车的出发时间且时间间隔要满足特定要求。
贪心算法最终结果为使用车底数量41由于step3中随机选择当前车底的可行车次导致每个车底的牵引车辆数相对有限考虑结合整数规划模型来获得当前车底的最优解决方案。
混合贪心算法 step1、初始化使用车底集合为C{}当前车底牵引车次集合D{}剩余车次集合P为上下行全量车次 step2、计算剩余所有车次的前序车次数量和后续车次数量 step3、按照车辆的前序车次数和后续车次数进行排序 step4、将前序车次数和后续车次数量最少的车辆作为必选车次建立整数规划模型获取最优路径最大化彻底服务车次数 step5、将车底牵引计划添加到车底集合中更新剩余车次如果所有列车牵引完成转step6否则转step2 step6、输出车底牵引计划 step7、结束。
混合贪心算法最终使用的车底数量为36相比于贪心算法混合贪心算法主要在两个方面有所改进。一个是优先选择车前序和后续车次少的车次进行分配这是由于到了算法后期这样的车次往往一个车次就要完全占据一个车底。另外一个改进的点是采用整数规划能够真正意义上获取每个车底当前的最优选择。 从上述甘特图中也可以明显看出贪心策略的一些特征排序靠前的车底由于有比较大的选择空间牵引路径都比较长牵引负载比较大排序靠后的车底由于选择空间急剧收缩往往一个车底只能服务一两趟车次。
3.2 负载均衡调整
由于贪心策略产生的结果会出现负载极度不均衡的情况考虑采用局部调整策略对产生的方案进行调整。调整的思路很简单将负载比较高的车底服务的车次重新分配给负载比较低的车底即可其对应的基本流程如下 调整过后的结果如下从图上可以看出来调整之后的结果变得更加均衡了。
四、代码实现
4.1 贪心算法
def get_path(all_trains,from_trains,to_trains):used_trains[]all_path[]cnt0max_length22max_num[randint(18,22) for i in range(1000)]while len(set(used_trains))!len(all_trains):route_lengthmin(max_length,max_num[cnt])for i in range(route_length,0,-1):resultsolver_route(all_trains,from_trains,to_trains,used_trains,i)if result:breakelse:max_lengthi-1used_trainsresultall_path.append(result)cnt1return all_path4.2 整数规划
def solver_route(all_trains,from_trains,to_trains,used_trains,route_length):train_numlen(all_trains)# 创建模型model gp.Model(train_scheduling)# 数据处理new_from_trainsdeepcopy(from_trains)new_to_trainsdeepcopy(to_trains)for train in all_trains:new_from_trains[train]list(set(new_from_trains[train])-set(used_trains))new_to_trains[train]list(set(new_to_trains[train])-set(used_trains))io_num{}for i in range(len(all_trains)):trainall_trains[i]io_num[i]len(new_from_trains[train])len(new_to_trains[train]) dffpd.DataFrame(io_num.items(),columns[key,value])sort_trainsdff.sort_values(by[value],ascendingFalse)[key].valuesfix_train-1for train in sort_trains:if not train in used_trains:fix_traintrainbreak# 是否将站点i放置在位置jx {}for i in range(train_num):for j in range(route_length):x[i,j] model.addVar(vtypeGRB.BINARY, namefx_{i}_{j})# 目标函数obj0for i in range(train_num):for j in range(route_length):objio_num[i]*x[i,j]model.setObjective(obj,GRB.MINIMIZE)# 每个位置最多有一个节点for j in range(route_length):expr0for i in range(train_num):exprx[i,j]model.addConstr(expr1)# 节点之间要有连关系for j in range(route_length-1):for i in range(train_num):expr0trainall_trains[i]for ii in from_trains[train]:exprx[ii,j]model.addConstr(exprx[i,j1])# 遍历过的车次不再选择for i in used_trains:expr0for j in range(route_length):exprx[i,j]model.addConstr(expr0)# fix train一定要满足expr0for j in range(route_length):exprx[fix_train,j]model.addConstr(expr1)# 求解model.setParam(OutputFlag, 0)model.setParam(GRB.Param.TimeLimit, 60)model.optimize()# 检查求解器状态status model.Statusif status GRB.INFEASIBLE:return []else:return get_result(x,train_num,route_length)局部调整
paths[]
for idx,row in result.iterrows():patheval(row[0])paths.append(path)for i in range(len(paths)):pathpaths[i]remove_trains[]path_durationget_path_duration(path)print(path_duration)for train in path:if path_durationavg:breakfor j in range(i1,len(paths)):add_pathpaths[j]add_path_durationget_path_duration(add_path)if add_path_durationavg:continueidxget_insert_index(train,add_path)if idx0:add_path.insert(idx,train)remove_trains.append(train)path_duration-(train_info.end_time-train_info.start_time)breakfor train in remove_trains:paths[i].remove(train)
