时间窗车辆路径问题【带有时间窗约束的车辆路径问题的一种改进遗传算法】

系 统

管理学报

第１９卷

不同，文献［６］中１００，本文３０；③文献［６］中没有给出２０次求解中有多少次求得最优解，本文算法在软硬２种时间窗下，求得最优解的概率分别为９０％和７５％。由此可以看出本文算法具有较快的收敛速度和较高的稳定性。

表２实例ｌ。软时间窗下算法运行结果

第２个实例［６］，该问题有８个客户，顾客的装货或卸货的时间为Ｔｉ，一般将ｔ作为车辆的行驶时间的一部分计算费用，ｇｆ和［ｎ，，６ｉ］的含义同前，具体数据见表４。这些任务由仓库发出的容量为８ｔ的车辆来完成，车辆行驶速度为５０，仓库以及各个顾客之间的距离见表５。

６），达到最优解的概率为８０％，其最终结果与文献［６］中相同最优解其费用值为９１０，对应的子路径

为（Ｏ一３一ｌ一２—０）、（Ｏ一６—４一Ｏ）、（Ｏ一８—５—７一Ｏ）。然而，文献

［６］是在ｍａｘｇｅｎ＝５０、ｐｏｐｓｉｚｅ一２０的情况下，达到最优解的概率为６７％。这又说明了本文算法的有

效性。

表６实例２的算法运行结果 ４ 结语

尽管用带有子路径分隔符的自然数编码作为遗传算法解决ＶＲＰＴＷ问题的编码方式有其优点，但缺陷也是显而易见的，为了弥补该缺陷，本文去掉了

子路径中的分隔符，并采用Ｓｐｌｉｔ作为解码方式，就此设计了求解ＶＲＰＴＷ的遗传算法，并进行了数值试验的对比分析，试验结果表明，该算法是十分有

效的。参考文献

ＤａｎｔｚｉｑＧ，Ｒａｍｓｅｒ

Ｊ．Ｔｈｅｔｒｕｃｋｄｉｓｐａｔｃｈｉｎｇｐｒｏｂｌｅｍ

［Ｊ］．Ｍａｎａｇｅｍｅｎｔ

ｓｃｉｅｎｃｅ，１９５９，１３（６）８０一９１．

谢秉磊，李军，郭耀煌．有时间窗的非满载车辆调

度问题的遗传算法［Ｊ］．系统工程学报，２０００，１５

（３）２９０一２９４．

宋伟刚，张宏霞，佟玲．有时间窗约束非满载车辆调度问题的遗传算法［Ｊ］．系统仿真学报，２００５，１７

（１１）２５９３—２５９７．

刘诚，陈治亚，封全喜．带软时间窗物流配送车辆路径问题的并行遗传算法

［Ｊ］．系统工程，２００５，２３

（１０）７—１１． 亓

霞，陈森发．基于改进小生境ＧＡ的有时间窗物

流配送路径优化问题研究［Ｊ］．管理工程学报，２００６，

２０（１）７９—８３．

林丹，丑英哲，王萍．求解车辆路径问题的一种遗传算法［Ｊ］．系统工程理论方法应用，２００６，１５

（６）５２８—５３３．

张智海，吴星玮．带时间窗车辆路径问题的并行遗传

算法［Ｊ］．工业工程，２００７，１０（３）１１１—１１４．

Ｓｃｈｍｉｔｔ

Ｌ

Ｊ．Ａｎ

ＥｍｐｉｒｉｃａｌＳｔｕｄｙ

Ｃｏｍｐｕｔａｔｉｏｎａｌ

ＳｔｕｄｙｏｆＧｅｎｅｔｉｃＡｌｇｏｒｉｔｈｍｓｔｏ

Ｓｏｌｖｅ０ｒｄｅｒＰｒｏｂ—

ｌｅｍｓＡｎＥｍｐｈａｓｉｓｏｎ

ＴｓＰａｎｄ

ＶＲＰＴＣ［Ｄ］．Ｕｎｉ—

ｖｅｒｓｉｔｙｏｆ

Ｍｅｍｐｈｉｓ，１９９４．