求解带硬时间窗车辆路径问题的改进UMDA 算法

交通运输系统工程与信息 ›› 2016, Vol. 16 ›› Issue (2): 176-182.

求解带硬时间窗车辆路径问题的改进UMDA 算法

柴获^a,b，何瑞春*^b，马昌喜^b，代存杰^a,b

兰州交通大学a. 机电技术研究所；b. 交通运输学院，兰州730070

收稿日期:2015-09-29 修回日期:2015-11-22 出版日期:2016-04-25 发布日期:2016-04-25
作者简介:柴获(1982-), 男, 甘肃静宁人, 讲师, 博士生.
基金资助:
国家自然科学基金/National Natural Science Foundation of China(61364026,51408288)；兰州交通大学校青年基金/ Youth Foundation of Lanzhou Jiaotong University(2015026)；兰州市科技计划项目/Science and Technology Planing Project of Lanzhou(2014-1-172).

A Univariate Marginal Distribution Algorithm Hybridized with Insertion Heuristics for the Vehicle Routing Problem with Hard Time Windows

CHAI Huo^a，b，HE Rui-chun^b，MAChang-xi^b，DAI Cun-jie^a,b

a. Mechatronics Technology and Research Institute; b. School of Traffic and Transportation，Lanzhou Jiaotong University， Lanzhou 730070，China

Received:2015-09-29 Revised:2015-11-22 Online:2016-04-25 Published:2016-04-25

摘要/Abstract

摘要：

针对带硬时间窗的车辆路径问题(VRPHTW)求解，提出了一种混合单变量边缘分布算法(hybrid UDMA，hUDMA)，改进了基本UMDA的概率模型.统计节点按路径分布的概率，使其能够在解空间上找到节点—路径的分布关系，提高了UMDA的全局搜索能力.采用两阶段插入法进行最佳节点搜索和路径分配完成UMDA采样操作，通过种群进化来获取最优解.计算Solomon 100 客户的6 类问题56 个算例的实验结果表明：在最优解的取得方面，C类算例能够全部取得最优解，R、RC类算例能以50%左右概率取得最优解；在平均误差方面，C类算例计算结果与已知最优解一致，R、RC类算例计算误差率与已知最优解比较接近，平均误差率为1.03%.

关键词: 交通工程, 分布估计算法, 单变量边缘分布算法, 带时间窗车辆路径问题, 概率模型, 插入法

Abstract:

This paper presents a univariate marginal distribution algorithm hybridized with insertion heuristics for the vehicle routing problem with hard time windows (VRPHTW). In the VRPHTW，a fleet of vehicles must deliver goods to a set of customers，time window constraints of the customers must be respected and the fact that the travel time between two points depends on the time of departure has to be taken into account. The latter assumption is particularly important in an urban context where the traffic plays a significant role. A shortcoming of univariate marginal distribution algorithm for vehicle routing problems is that，customers are not independent events in probabilistic model. Hence，we propose a novel probabilistic model that probability of the distribution of customers delivered by the same vehicle. Moreover，the new population is generated by two phase insertion heuristics method. Computational results with 56 Solomon benchmark problems confirm the benefits of other algorithms，the resulting algorithm turns out to be competitive，matching or improving the best known results.

Key words: traffic engineering, estimation of distribution algorithms, univariate marginal distribution algorithm, vehicle routing problem with time windows, probabilistic model, insertion heuristics

中图分类号:

U492.3

柴获，何瑞春，马昌喜，代存杰. 求解带硬时间窗车辆路径问题的改进UMDA 算法[J]. 交通运输系统工程与信息, 2016, 16(2): 176-182.

CHAI Huo，HE Rui-chun，MAChang-xi，DAI Cun-jie. A Univariate Marginal Distribution Algorithm Hybridized with Insertion Heuristics for the Vehicle Routing Problem with Hard Time Windows[J]. Journal of Transportation Systems Engineering and Information Technology, 2016, 16(2): 176-182.

导出引用管理器 EndNote|Ris|BibTeX

链接本文: http://www.tseit.org.cn/CN/abstract/abstract19174.shtml

http://www.tseit.org.cn/CN/Y2016/V16/I2/176

参考文献

[1] Mühlenbein H，Paaß G. From recombination of genes to the estimation of distributions I. Binary parameters[C]. Lecture Notes in Computer Science Volume，Vol.1141， proceedings of the 4th International Conference on Parallel Problem Solving from Nature，London，UK， 1996:178-187.

[2] Mühlenbein H. The equation for response to selection and its use for prediction[J]. Evolutionary Computation， 1997，5(3): 303-346.

[3] Hauschild M，Pelikan M. An introduction and survey of estimation of distribution algorithms[J]. Swarm and Evolutionary Computation，2011，1(3):111-128.

[4] Zhang Q. On stability of fixed points of limit models of univariate marginal distribution algorithm and factorized distribution algorithm[J]. IEEE Transactions on Evolutionary Computation，2004，8(1):80-93.

[5] Kim D W, Ko S，Kang B Y. Structure learning of bayesian networks by estimation of distribution algorithms with transpose mutation[J]. Journal of applied research and technology，2013（11）: 586-596.

[6] Hashemi M， Meybodi M R. Univariate marginal distribution algorithm in combination with extremal optimization (EO，GEO) [C]//Proc. 18th International Conference on Neural Information Processing (ICONIP’ 11)，2011:220-227.

[7] 顾巍. 基于分布估计算法的水库群联合优化调度研究[D]. 武汉: 华中科技大学，2013. [GU W. Research on optimal scheduling of cascaded reservoirs based on estimation of distribution algorithm[D]. Wuhan: Huazhong University of Science and Technology，2013.]

[8] Savelsbergh M. Local search for routing problem with time windows[J]. Annals of Operations Research，1985， 16(4): 285-305.

[9] Anbuudayasankar S P，Ganesh K，Sanjay Mohapatra. Models for practical routing problems in logistics[M]. Springer International Publishing Switzenrland，2014.

[10] 孟祥虎，胡蓉，钱斌. 求解带时间窗车辆路径问题的有效混合PBIL算法[J]. 系统工程理论与实践，2014，34 (10)：2701- 2709. [MENG X H，HU R，QIAN B. Effective hybrid population-based incremental learning algorithm for vehicle routing problem with time windows[J]. Systems Engineering - Theory & Practice， 2014，34(10)：2701-2709.]

[11] Kytojokia J，Nuortio T，Brays O，et al. An efficient variable neighborhood search heuristic for very large scale vehicle routing problems[J]. Computers & Operations Research，2007，34(9): 2743-2757.

[12] Vaira G，Kurasova O. Genetic algorithm for VRP with constraints based on feasible insertion[J]. Informatica， 2014，25(1): 155-184.

[13] 周树德，孙增圻. 分布估计算法综述[J]. 自动化学报， 2007，33(2): 113-124. [ZHOU S D，SUN Z Q. A survey on estimation of distribution algorithms[J]. Acta Automatica Sinica，2007，33(2):113-124.]

[14] Dhahri A，Zidi K，Ghedira K. A variable neighborhood search for the vehicle routing problem with time windows and preventive maintenance activities[J]. Electronic Notes in Discrete Mathematics，2015（47）: 229-236.

[15] Balseiro S R，Loiseau I，Ramonet J. An ant colony algorithm hybridized with insertion heuristics for the time dependent vehicle routing problem with time windows[J]. Computers & Operations Research，2011 （38）: 954-966.

[16] Jung S，Ramon B. A hybrid genetic algorithm for the vehicle routing problem with time windows[C]// Proceedings of Genetic and Evolutionary Computation Conference，2002:1309-1316.

[17] Ombuki B M，Ross B，Hanshar F. Multi- objective genetic algorithms for vehicle routing problem with time windows[J]. Applied Intelligence，2006，24(1)：17-30.