插入算法求接送顾客到机场的车辆调度问题

《插入算法求接送顾客到机场的车辆调度问题》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、第26卷第1期控制理论与应用Vol.26No.12009年1月ControlTheory&ApplicationsJan.2009文文文章章章编编编号号号:1000¡8152(2009)01¡0092¡05插插插入入入算算算法法法求求求接接接送送送顾顾顾客客客到到到机机机场场场的的的车车车辆辆辆调调调度度度问问问题题题孔媛,唐加福,董纲,张军(东北大学流程工业综合自动化教育部重点实验室,辽宁沈阳110004)摘要:根据票务公司免费接送顾客服务的特点,将顾客服务的满意度量化为顾客到达机场的时间,在一定的满意度及绕行限制下,提出了一种车辆路径模型来描述接送顾客服务的车辆调

2、度问题.根据模型的特点,设计了新的评价因子并提出了一种基于最小评价因子的顺序插入方法.大量的仿真实验与比较,验证了模型和算法的有效性.关键词:接送服务;时间满意度;车辆路径问题;插入算法中图分类号:TP273文献标识码:AAninsertionalgorithmforvehicleschedulinginpickingupanddeliveringcustomerstoairportKONGYuan,TANGJia-fu,DONGGang,ZHANGJun(KeyLaboratoryofIntegratedAutomationofProcessIndustrialof

3、MOE,ShenyangLiaoning110004,China)Abstract:Accordingtothecharacteristicsoffreeserviceinflightticketsales,avehicleroutingproblem(VRP)modelisproposedtodescribetheschedulingprobleminpickingupanddeliveringcustomerstoairport.Inthismodel,thecustomers’satisfactionisquantifiedbythetimeconsumedinre

4、achingtheairport.Thecustomers’satisfactionandthevehicles’routeareconsideredsimultaneouslyasconstraints.Then,asequentialcheapestinsertion(CI)Heuristicbasedonanewappraisal-factorisdevelopedfordeterminingthismodel.Alotofcomputationalexperimentsaredoneandanalyzedtoshowtheeffectivenessofthep

5、roposedmodelandalgorithm.Keywords:serviceofpick-upanddelivery;time-basedsatisfactiondegree;vehicleroutingproblem;insertionalgorithm1引引引言言言(Introduction)径问题(vehicleroutingproblem,VRP)[1»3]的一种延免费接送顾客到机场是航空票务公司推出的一伸与应用.与VRP相比,VSPA具有5个显著的扩展特项新型优惠服务.以往航空公司接送顾客提供的机征:1)一般航空公司有办理登机手续的时间限制,场巴士服务

6、是收费的,每天在固定几个发车时段和顾客不希望到达机场太早或太晚;2)顾客分布在一站点发车,顾客要自行到站点集合,统一乘车前往机天当中的各个航班上,因此顾客到达机场的时间比场.机场巴士虽然在某种程度上降低了顾客的花销,较分散;3)在接送服务中,车辆会在满足顾客要求但对顾客的搭乘时间和地点都有严格的限制,给顾和能力约束下,尽可能一次接送更多的顾客,这样客造成不便.与之相比,航空票务公司采用小型巴士会带来绕行问题,顾客希望有车辆绕行的距离约束;免费上门接送顾客,提高了顾客满意度和公司信誉,4)VSPA使用接送顾客的小型巴士一般为小轿车,载但同时增加了服务成本.因此在满足所有

7、顾客要求客量比较小,只容纳4人;5)顾客分布于一个城市的的前提下,票务公司需要制订合理的车辆分配和调不同区域,地理位置相对分散.度计划,安排接送的车辆,每辆车的发车时间和接送国内外有关VRP的研究很多,而且也日益细的顾客及接送顺序,以降低服务成本.化[1].但由于VRP本身是NP-hard问题,它的各个扩接送顾客到机场的车辆调度问题(vehicle展更是难上加难,大多是通过启发式算法来获得近schedulingproblemforair-passenger,VSPA)是车辆路似最优解.关于VSPA问题,在文献[4]中,作者曾将满收稿日期:2007¡0