资源描述：
《不确定车辆数的有时间窗车辆路径问题的遗传算法》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。
1、2004年6月系统工程理论与实践第6期文章编号:100026788(2004)0620134205不确定车辆数的有时间窗车辆路径问题的遗传算法邹彤,李宁,孙德宝(华中科技大学控制科学与工程系,湖北武汉430074)摘要:给出了不确定车辆数的有时间窗车辆路径问题(VRPTW)的数学模型,提出一种基于客户的编码表示方式,可以表示出不同的车辆数,实现VRPTW的路径长度和车辆数的同时优化,并用计算实例进行了验证,同时对计算中涉及的一些问题进行了讨论L关键词:有时间窗的车辆路径问题;不确定车辆数;遗传算法中图分类号
2、:O221;U116.2文献标识码:AGeneticAlgorithmforVariableFleetVehicleRoutingProblemwithTimeWindowZOUTong,LINing,SUNDe2bao(DepartmentofControlScienceandEngineering,HuazhongUniversityofScienceandTechnology,Wuhan430074,China)Abstract:Becausethefixedcostofavehicleismuchm
3、orethantherunningcost,itiseffectivetocutdownthetotalcosttoseektheminimumnumberofvehiclesinVehicleRoutingProblemwithTimeWindow(VRPTW).ThispaperpresentsamathematicalmodelofvariablefleetVRPTW.AnewchromosomecodethatcanexpressvariousvehiclenumberinGeneticAlgori
4、thm(GA)isdevelopedfromthecodebasedoncustomers.TheGAcansearchforoptimalsolutiononbothroutelengthandvehiclenumber,whichisprovedbyanexperiment,andseveralpointsintheoptimalprocessarediscussed.Keywords:vehicleroutingproblemwithtimewindow;uncertainvehiclenumber;
5、geneticalgorithm1引言车辆路径问题(VehicleRoutingProblem,VRP)最早是由Dantzig和Ramser于1959年首次提出的,它是指有一定数量的客户,各自有不同数量的货物需求,一个中心仓库提供这些货物,并有一个车队负责分送货物,要求组织适当的行车路线,使客户的需求得到满足,并能在满足一定的约束条件下,达到诸如路程最短、成本最小、耗费时间最少等目的L有时间窗车辆路径问题(VehicleRoutingProblemwithTimeWindow,VRPTW)是在基本VRP中对
6、每个客户的开始服务时间范围加以约束,与实际情况更加吻合,因此有很强的实用背景L由于VRPTW是NP-难问题,所以对该问题的研究集中在各种启发式算法上,而遗传算法是其中研[1][2]究得较多的一种方法LTan采用了变长编码方式的MessyGeneticAlgorithm,Ozdemir使用了一种基[3][4]于图的进化算法,Hwang则对遗传算法的交叉、变异算子进行了改进,而Baker将一种隐含编码方式的遗传算法用来解决该问题,等等L由于出动一辆车的固定成本远远大于车辆的行驶成本,对于一个具体的问题,寻求能完
7、成任务的最少车辆数是减少成本的有效方法,但一些复杂的问题(如VRPTW)无法事先确定合适的车辆数,需要优化算法进行计算L目前,对VRP的研究多以确定的车辆数目来求解,对不确定车辆数的问题涉及较少,如文[5],其实现方法是将客户需求之和除以车辆容量,得到最少车辆数,然后进行求解,实际上仍然是确定车辆数的车辆路径问题L这种方法简单、实用,但适用于只有车辆容量约束的车辆路径问题,而对于有时间窗收稿日期:2003207203作者简介:邹彤(1971-),男,博士研究生,研究领域为复杂系统仿真、演化算法,Email:
8、tong.zou@163.com第6期不确定车辆数的有时间窗车辆路径问题的遗传算法135的车辆路径问题,如果这样处理,很可能不满足时间窗的约束要求L本文主要是对遗传算法来求解不确定车辆数的有时间窗车辆路径问题进行了研究,提出了一种新的编码方式,使遗传算法在计算过程中能自动寻找满足要求的最少车辆数L第2节给出了不确定车辆数的有时间窗车辆路径问题的问题描述和数学模型,在第3节详细介绍了该遗传算法的编码表示及相应的遗传
