分车收发车辆路径问题的三个启发式算法之比较

Comparison among Three Heuristic Algorithms for SVRPPD

车辆路径问题已经出现了很多的变种.在这些扩展的VRP问题当中,分车收发车辆路径问题就是其中之一.本文针对这一问题在已有的模型上加以改进,并且提出了摆脱车辆数限制的最远点拼车算法和竞争决策算法。最后结合最远点完全拼车算法通过数值实验对三者进行了比较.结果显示竞争决策算法得到的结果好于其他两者,其次是最远点拼车算法。

Many variations for Vehicle Routing Problem（VRP）have appeared.But among these expansions,the reasearch in Split Vehicle Routing Poblem with Pick-ups and Deliverys（SVPRPD）is little yet.In this paper,an improved model for SVRPPD is put forward.Furthermore one heuristic algorithm called the Farthest Node Split Load Algorithm（FNSL）and one Competiative Decision Algorithm（CDA）,which get rid of the constraint of the minimum vehicle number are put forward also.In the end,some computational experiments are done to compare among these two algorithms and Farthest Node Full Load Algorithm（FNFL）.As a result,CDA is the best,and FNFL next-best.