单车场集送一体化车辆路径问题及其混合算法研究(论).pdfVIP

第3l卷 第5期 武汉理工大学学报(鸯圣鍪差) VoI．31No．5 2007年10月 ofWuhan of Oct．2007 Journal UniversityTechnology (TransportationScience＆Engineering) 单车场集送一体化 车辆路径问题及其混合算法研究 屈 援1’∞汪 波钟石泉” (天津大学管理学院”天津300072)(暨南大学管理学院”广州 510632) 搞薹；针对物流配进中的单车场集迸一体化车辆调度问题提出了基于禁忌规则的模拟退火算法． 采用了基于自然数的一体化配迸对路径表示方式，用里程约柬来控翻车场的插人，以增加惩罚的 方式加入时间窗约束．算法在状态生成函数中利用3种邻域扩大抽样范围；根据同题的特点，在模 拟退火算法抽样过程中加入了禁忌规则．舟绍了算法的原理，应用算法求解了多个有代表意义的 同题实例．对算例结果进行分析表明，该算法可以有效地求得有里程和时间窗约束的单车场集进 一体化车辆调度问题的优化解． 关键词；车辆路径问题}禁忌算法；模拟退火算法 中图法分类号，U492．3 车辆路径同题(vehicle routingproblem，送货点研卸货，则蛳，n称为一个配送对，撕称为 VRP)自1959年Dantzig和Ramser首先提出以 配送对前点，研成为配送对后点．配送车辆在安排 来，就引起了人们的高度重视．VRP的实用性强， 行车路线的时候，要考虑两点：一是车辆必须是先 应用广泛“]． 到％再到¨二是如果车辆到了m，则下一个配送 已有的VRP成果口4]，基本上是对单送货或点必须是。t．这样就能够保证配送车辆在各个配 单集货的车辆路径问题的研究，都是单独的客户 送对之间有次序地集货和送货． 点．而另一类VRP问题要考虑客户之间的关系， 1．2问题的描述 集送一体化问题就是其中一种．目前对集货送货 (1)物流配送渠道由1个车场，≈个送货点 一体化VRP的研究还比较少，文中将对单车场集 (配送对后点)，n个集货点(配送对前点)组成，配 送一体化车辆路径问题进行研究，并且提出一种 送对前、后点一一对应；(2)车辆从车场出发，完 基于禁忌规则的模拟退火算法对单车场集送一体 成配送任务后返回原车场，(3)配送车辆有最大 化车辆路径问题进行优化，最后通过算例结果及 配送距离约束；(4)每个配送对有服务时问窗约 其分析验证了算法的有效性． 束，要求配送车辆在时间窗内到达客户点}(5)优 化目标为车辆完成所有配送任务的总路程最短． 1 问题的描述 2 含有禁忌规则的模拟退火算法设计 1．1配送对 如果配送车辆的容量为g，i配送点配送量为 禁忌算法(TabuSearch，TS)的优点是有哪些信誉好的足球投注网站 毋，对于大部分任务有丢g≤毋≤口的非满载车辆 速度快，局部爬山能力强，缺点是容易陷入局部最 优化调度问题，配送点之间有两两相互对应的关 优解．模拟退火算法(simulated