论文研究-基于集划分的精确算法求解机场接送车辆调度问题.pdf

所需积分/C币:10 2019-09-20 17:50:38 687KB .PDF
5
收藏 收藏
举报

论文研究-基于集划分的精确算法求解机场接送车辆调度问题.pdf,  通过对免费接送机场服务的进一步研究, 本文为基于租赁车辆模式的票务企业提出了用于求解发车次数与顾客满意度均衡模型的基于集划分的精确算法. 在该算法的设计过程中, 综合考虑了机场接送服务中顾客对接送时间窗, 到达机场时间窗以及绕行限制的要求. 最后通过一系列实例的计算分析, 验证了该算法用于求解免费接送机场服务车辆调度问题的有
1684 系统工程理论与实践 第33卷 e,l],如果车辆到达机场的时间t(t1=tn+1)在顾客期望的时间段内则顾客满意度为100%.反之如果车 辆到达机场的时间过早或过晚对于顾客来说都是不可接受的,因此顾客对到达机场硬时间窗要求为ea,1 如果车辆到达机场的时间超出该时间范围则顾客满意度为0.显然[e,1≤e,1]本文用一个线性分段 函数Sa()来描述顾客到达机场满意度函数,如下所示: t t,t∈,4 t iEe 同理顾客接送时间窗满意度函数可描述如下 在描述顾客接送时间窗满意度函数时,t表示车辆到达顾客点讠的时问,讠的取值范围为{1,2,…,m} 综上所述,顾客整体满意度函数可表示为 5(y)Sn=1(S2()+5(1) 2 33企业满意度描述 本文为基于租赁车辆模式的票务企业提供车辆分配与调度方案,企业的人均运输费用只与调度中所用车 辆数有关,与车辆路径无关.因此企业的人均运输费用可描述如下: F C k=1 上式中C表示企业人均运输费用,P表示顾客总人数,F表示车辆的固定发车费用,M表示完成一个计划 周期内的调度所需要的总车次数.在顾客总人数P一定的情况下,发车次数M越小.人均运输费用C就越 山于免费接送机场服务是一项增值服务,因此票务公司在免费接送服务中对顾客的人均运输费用有一定 的要求.本文用Co表示企业期埊的人均运输费用,用C〃来表示企业叮接受的最大人均运输费用.当企业 的实际人均运输费用小于或等于Co时,企业满意度为100%,当企业的实际人均运输费用超过Cm时,则表 示要完成本次服务企业需要投入的成本太大,其满意度为0;当企业的实际人均运输费用介于Co和Cm时, 企业满意度随着运输费用的增大而减小,企业满意度两数S(e)可描述如下 Cm-c Co <C<cma 0. 上式中的r(r>0)表示企业对风险的偏好,具体值由企业决定,本文中取r=1 3.4车次数与顾客满意度均衡模型 通过分析可知,对于顾客而言,企业的发车次数越多,将顾客送到机场的时间越能接近顾客期望的时间, 顾客的满意度也就越大.但是企业的人均运输费用乜随之增加,因此顾客满意度和企业人均运输费用之间的 关系可由图1模糊表示 通过上述分析叮知,当顾客满意度卜限要求增大时,人均运输费用增大,企业满意度随之降低,因此在该 项服务中顾客满意度和企业满意度是相互冲突的机场接送服务中的均衡问题即可措述为在顾客满意度和企 业满意度之间找出一个最佳均衡点 用a表示企业满意度与顾客满意度之间的平衡水平,cmax表示顾客满意度与企业满意度之间的最佳平 衡点,C*表示最佳平衡点处的人均运输费用,c0表示顾客满意度下限要求.故均衡模型可用图2表示9 第7期 曹夏夏.等:基于集划分的精确算法求解机场接送车辆调度问题 1685 图1顾客满意度和企业人均运输费用的关系 图2顾客满意度和全业满意度的均衡情况 其数学模型可描述如下 max C ∑2z=1 ∑∑2 ∑Zn+12 ∑2-∑2 ≤Qk=1,2 8 -1, C≤t≤li=1,2,…,n;k=1,2, (10) t+1≤142k=1 BDn+1>2(4-1+∑(-(2+2m1D(m+1 1.2. 1.2 0 S(e)≥aoi=1,2,,n 0≤a0≤a≤1 (16) 2∈{0,1}V(,)∈A,k∈V,Z=0 2∈{0,1}k=1,2 上式中:(1)目标函数;(2)企业满意度约束;(3)顾客满意度约束;(4)和(5)保证每个顾客点被访问 次;(6)保证每个从车场出发的车辆都完成了服务,将顾客送劉了机场;(7)进入顾客点的车次和从该顾客点 驶出的车次数守恒;(⑧)车辆容量约束:(9)两个顾客点之间的服务时间约束;(10)接送顾客时间约束:(1)车 次到达机场的时间约束:(12)绕行约束:(13)和(14)接顾客的时间和车辆到达机场的时间都在满意度下限 要求范围之内;(15)企业满意度也在满意度下限要求范围之内:(16)满意度的取值范围;(17)和(18)决策变 量的取值范围. 1686 系统工程理论与实践 第33卷 4基于集划分的精确算法 e={1,2,…,n}表示当前周期的顾客点集合,顾客点定义为航班出发时刻,地理位置和接送时间窗相 同的一类顾客的集合.基于划分规则进行分类的第讠个顾客点集合为S(i=1,2,…,M),M表示顾客点集 合的个数,满足∪S=Ne,D,;表示顾客点讠到顾客点j的距离.算法流程描述如下: Step1初始化,讠=1,S;=W; Step2将N中顾客点根据顾客到达机场时间窗的起始时刻从早到晚排序; step3初始化顾客满意度下限ao; Step4计算N中顾客点j在满意度下限ao要求下的接送时间窗l,l和到达机场的时间窗e,l 1.2 Step5基于到达机场时间窗的顾客点集合的划分,按如下步骤生成集合S1 Step5-1判断N是否为空,若N不为空,依次以N2中的顾客点i作为种子Pse,S;-Psen,顺 序遍历N中未处理的顾客点c,若e≤l,则S2=S∪{c},N=N-{h;若l<c,则i=2+1,转 到Step51 Step6找出集合S(i-1,2,……,M)中满足车辆容量限制的所有可能的路径r和由路径r组成的路 径集合R Step7检验路径集合R中的路径γ是否满足绕行限制 设路径一共有m个顾客点o为车场,d=m+1为机场,β为绕行限制系数.当满足对s∈ {1,2.…,m}都有∑=。Dkk+1≤BDd时(k表示路径r上的第k个顾客点).路径r满足绕行限制,否 则不满足绕行限制,将路径r从路径集合P中删除; Step8检验路径r是否满足接送时间窗的限制; 气表示车辆服务路径γ时的发车时间,,表示路径r中第k个顾客点在满意度下限要求下的接送 时间窗,[e,l表示路径中所有顾客点在满意度下限要求下到达机场时间窗的交集设tmim为发车时间下 限,lmax为发车时间上限,lmin和lmax分别根据模型(M1)和模型(M2)用 Cplex求解而得: mIn l;+ -1,k <lL=1,2 L D l;+ L n+1 C max ≤l2+∑≤L D <li+ k-1,k <lu L=In+1 k=1 当tma>tmin时,表示该路径满足接送时间窗限制,否则不满足,将路径r从路径集合R中删除; Step9根据模型(M3)用 Cplex求出路径上顾客满意度最大时的发车时间t和该发车时间下的路 径γ上的顾客满意度总和S=max +1 maX st.ek≤t+ ∑ k-1,k L=1.2 m k-1,k∠nd 第7期 曹夏夏.等:基于集划分的精确算法求解机场接送车辆调度问题 1687 Step10根据集划分模型10-13(M)用 Cplex求出完成调度所需要的最少车次数M1; min (M4) ∈{1,2 r=1 0or1y∈{1,2,…,N} 上式中xr表示车次,ar是一个二进制变量,如果ax=1,表示顾客点在路径r上,否则表示顾客点 不在路径r上. Step11根据模型(M5)用 Cplex求出顾客满意度最大时完成调度所需要的车次数M2 indx 1.y2y 1i∈{1,2,…,n} =0or1 ∈{1,2,…,N} Step12由上述可知,完成调度需要的车次数集合为M={M1,…,M2},根据一定车次数下满意度最 大集划分模型(M6),分别求出车次数为M1,…,M2的每个调度方案的顾客满意度S(c)和企业满意度S(e) Ⅲax∑s st ∈{1 m∈M 0or1r∈{1,2 step13根据曹夏夏等提出的均衡模型可知,max{Sm(e)∧Sm(c),m∈M}为最佳均衡水平,其对 应的调度方案为最佳均衡调度方案 在机场接送服务中,同一个车辆所接的顾客在同一时间到达机场,因此同一个车次上的顾客所要求的到 达机场时间窗必须要有交集,并还需满足车辆容量限制.上述算法中的 Step 1-Step6计算出了满足这两者 限制的所有可能的路径集合R;Step7和Ste8删除了集合R中不满足绕行和接送时间窗限制的路径;Step 9为每条路径确定了一个发车时间,并且在该发车时间下,可以获得该条路径上的最大顾客满意度;Step10 tep13计算出了完成一个周期的服务所需要的所有可能的发车次数,通过对不同车次数的比较分析,求出 顾客满意度和企业满意度的最住均衡点以及该点所对应的完成服务所需要的最佳发车次数.由于该算法考 虑了调度中所有可能的情况,因此该算法能够精确地求解接送机场服务中发车次数与顾客满意度均衡问题 5计算实验与结果分析 51实验设置 根据实际调研,航空票务公司每天从早晨6:00到下午18.00需要接送的顾客约100300人.98%的顾客 期望在登机时刻前3060分钟之间到达机场.90%的顾客可以接受的绕行限制系数为1.2-2之间.本文采用 随机产生的算例,设某时段(6:00-18:00)航空票务公司有顾客需要接送,它们分布在边长为60km的矩形区 域内车场坐标为(1,5),机场坐标为(60,60),车辆行驶速度为60km/h,绕行限制系数为1,车辆容量为4, 固定发车费用为70.整个算法是在 Core2PC,2.0GHz,1.000内存的计算札上Ⅴ isual studio2008环 境下,用C#语言编写而成 52计算实验与结果分析 由大量实例的计算结果可知,最佳均衡水平跟一个计划周期内需要服务的顾客点的地理位置分布,顾客 点的数量,顾客要求的接送时间窗和到达机场时间窗的宽度等因素有关,本文的测试实例信息由表1所示 1688 系统工程理论与实践 第33卷 表1实例信息表 实例 12 4 10 11 13 顾客点分布区域(KM2)20*2030*3040+4050*5060+6060*6060*6060*6060*6060+6060*6060+6060*60 顾客点数量 1001001001001001201401608 100100100100 时间窗宽度(m) 30 30 30 30 30 302421 18 表2实例运行时间表 实例 2 5 6 9 10 运行时间(ns)24332386237121992678367541201248220024012301 1)分析实例的运行时间 由表2可知,实例的运行时间主要由实例规模(即顾客点数量)决定.实例1-11的运行时间均不超过5 秒.根据实际调研,航空票务公司每天从早晨6:00到下午18:00需要接送的顾客约100300人.表1中测试 实例的顾客点范围为80-160,顾客人数范围是190-362.实际的调研数据在本文测试实例规模范围之内,同 时本文也对顾客点为200,250和300顾客人数分别为476,524,620)的大规模实例进行了测试,其运行时间 分别是7s,10s和15s,运行时间也在票务公司叮接受的范围之内,因此,该算法叮以有效地解决接送札场服 务中的午次分配与调度问题 2)分析顾客点的地理位置分布对最佳均衡水平的影响 100.00 98.00% 96.00% % 最 9508% 94.00% 均 3.50% 衡 92.00% 水 1.30 90.00% 88.000 86.00% 60°6050*5040*4030*3020*20 顾客点所占地理位置区域 图3顾客点位置分布对最佳均衡水平的影响 图3是实例15的实验结果,影响这四个实例结果的主要因素就是实例中顾客点地理位置的分布.由图 β可知计划服务周期內的顾客点分布越密集,该实例的最佳均衡水平越高 3)分析顾客点数量对最佳均衡水平的影响 100.00% 100.00% 98.00% 9800 96.00% 6.50 96.00 915% 最 ●499% 最94.00% 94.00% 3.03% 5,42% 9200% 衡 92.00 衡900% 水 水 89.03 9101% 平8800 90.00% 9.92 86.00% 88.00% 84.00% 8200% 100 120 140 160 5 18 24 顾客点数量 时间窗宽度 图4顾客点数量对最佳均衡水平的影响 图5时间窗宽度对最佳均衡水平的影响 图4是实例59的实验结果,影响这五个实例结果的主要因素是实例的顾客点数量.由图4可知,计划 服务周期内的顾客点数量越多,该实例的最佳均衡水平越高 4)分析时间窗的宽度对最佳均衡水平的影响 图5是实例5,10-13的实验结果,影响这四个实例结果的主要因素是接送时间窗和到达机场时间窗的 第7期 曹夏夏,等:基于集划分的精确算法求解机场接送车辆调度问题 1689 宽度由图5可知,计划服务周期内的顾客对到达机场时间窗和接送时间窗要求越宽松,最佳均衡水平越高 综上所述,该算法可以有效地求解机场接送车柄调度中的均衡问题,且更适合于求解顾客点数目较大,顾 客分布较密集以及顾客对服务时间窗要求较宽松的实例类型 6结论 本文为基于租赁车辆模式的票务企业提出了用于求解发车次数与顾客满意度均衡模型的基于集划分的 精确算法.在该算法的设计过程中,综合考虑了顾客对接送时间窗,到达机场时间窗以及绕行限制的要求.并 通过分析实例的顾客点分布,顾客点数量,时间窗宽度等信息对最佳均衡水平的影响,有效地验证了该算法 的适应性.从而为票务企业进行车次分配与调度提供合理的依据 参考文献 1 Solomon M. Algorithms for the vehicle routing and scheduling problems with time window constraints J. Oper ations Research, 1987, 35(2 ): 254-265 [2] Braysy O, Gendreau M. Vchicle routing problem with time windows, Part I: Route construction and local scarch algoriths[J. TransportaTion Science, 2005, 39(1): 104-118 3 Braysy O, Gendreau M. Vehicle routing problem with time windows, Part II: MetaheuristicsJ. Transportation 2005,39(1):119139 4 Tang J F, Pan Z D, Fung R Y K, et al. Vehicle routing problem with fuzzy time windows[J. Fuzzy Sets and Systems,2009,160(5):683695 ⑤唐加福,董纲潘震东,等.免费接送机场服务的多目标规划模型及算法J管理科学学抒,208,116):3542 Tang J F, Dong G, Pan Z D, et al. Multi-objective model and algorithm of free pickup customer and delivery to airport serviceJ. Journal of Mallagenent Sciences in China, 2008, 11(6):35-42 6]董纲,唐加福,孔媛,等免费接送机场服务的最小化成本模型及算法小]系统工程学报,2008,23(4):437-442 Dong g, Tang J F, Kong Y, et al. Minimum costs model and algorithm of free pickup and delivery customers to airport service[J. Journal of Systems Engineering, 2008, 23(4):437-442 7孔媛,唐加福,潘震东,等.基于集划分求解接送旅客到机场问题的启发式算法.东北大学学报,2009,30(5):625627 Kong y, Tang J F, Pan ZD, et al. A set-partition based heuristic algorithm to solve the problem of pick-up and delivery of air-passengersJ. Journal of Northeastern University. 2009, 30(5): 625-62 [8 Cao XX, Tang J F, Liu LL, et al. The vehicle routing and scheduling best balance model and algorithm for free pickup and delivery service in fight ticket sales companies[C// IEEE Fifth International Conference on Bio-Inspired Computing: Theories and Applications, Changsha, 2010: 343-349 9 Tang J F, Fung R Y K, XuB D, et al. A new approach to quality function deployment planning with financial consideration[ Computers &z Operations Research, 2002, 29(11):1447-1463 10 Baldacci R, Christofides N, Mingozzi A. An exact algorithm for the vehicle routing problem based on the set partitioning formulation with additional cuts J. Mathematical Programming, 2008, 115(2): 351-385 11 Chabrier A. Vehicle routing problem with elementary shortest path based column generation[J. Computers Operations Research, 2006, 33(10): 2972-2990 12 Dong G, Tang J F, Lai KK, et al. An exact algorithm for vehicle routing and scheduling problem of free pickup d delivery service in fight ticket sales companies based on set-partitioning model[J] Journal of Intelligent Manufacturing,2011,22(5):789799 13 Qureshi A G, Taniguchi E, Yamada T. An exact solution approach for vehicle routing and scheduling problems with soft time windows(J. Transportation Research Part E: Logistics and Transportation Review, 2009, 45(6) 960-977.

...展开详情
试读 8P 论文研究-基于集划分的精确算法求解机场接送车辆调度问题.pdf
立即下载 低至0.43元/次 身份认证VIP会员低至7折
一个资源只可评论一次,评论内容不能少于5个字
weixin_38744153 欢迎大家使用并留下宝贵意见
2019-09-20
  • 至尊王者

    成功上传501个资源即可获取
关注 私信 TA的资源
上传资源赚积分or赚钱
    最新推荐
    论文研究-基于集划分的精确算法求解机场接送车辆调度问题.pdf 10积分/C币 立即下载
    1/8
    论文研究-基于集划分的精确算法求解机场接送车辆调度问题.pdf第1页
    论文研究-基于集划分的精确算法求解机场接送车辆调度问题.pdf第2页

    试读结束, 可继续读1页

    10积分/C币 立即下载 >