工业工程

工业工程 ›› 2014, Vol. 17 ›› Issue (3): 101-107.

• 实践与应用 • 上一篇    下一篇

基于离散差分进化算法的随机车辆路径问题

  

  1. 1.天津师范大学 管理学院，天津 300387； 2.北京航空航天大学 经济管理学院，北京 100191
  • 出版日期:2014-06-30 发布日期:2014-07-14
  • 作者简介:侯玲娟(1984-)， 女，山西省人，讲师，博士，主要研究方向为物流系统的优化及算法.
  • 基金资助:

    国家自然科学基金资助项目(71071008)；天津市2012年度哲学社会科学研究规划项目(TJGL12-079)

A Novel Discrete Differential Evolution Algorithm for Stochastic VRPSPD

  1. 1.School of Management, Tianjin Normal University, Tianjin 300387,China; 2.School of Economics and Management, Beihang University, Beijing 100191, China
  • Online:2014-06-30 Published:2014-07-14

摘要： 针对差分进化算法求解组合优化问题存在的局限性，引入计算机语言中的2种按位运算符，对差分进化算法的变异算子进行重新设计，用来求解不确定需求和旅行时间下同时取货和送货的随机车辆路径问题（SVRPSPD）。通过对车辆路径问题的benchmark问题和SVRPSPD问题进行路径优化，并同差分进化算法和遗传算法的计算结果进行比较，验证了离散差分进化算法的性能。结果表明，离散差分进化算法在解决复杂的SVRPSPD问题时，具有较好的优化性能，不仅能得到更好的优化结果，而且具有更快的收敛速度。

关键词: 随机规划模型, 差分进化算法, 离散差分进化算法, 车辆路径问题(VRP)

Abstract: The stochastic vehicle routing problems with uncertain demand and travel time and with simultaneous pickups and deliveries(SVRPSPD) is a  typical combinatorial optimization problem. It is known that the basic differential evolution algorithm(DE)  is not suitable for solving combinatorial optimization problem. To overcome this drawback, a novel discrete differential evolution algorithm(DDE) is proposed by designing new mutation by introducing two bitwise operators of computer language. Then, the proposed algorithm is applied to SVRPSPD and the benchmark problem of VRP to validate the effectiveness of the proposed DDE algorithm. The simulation results are compared with the basic differential evolution algorithm and the existing genetic algorithm. Simulation results show that the DDE algorithm outperforms the others．Not only DDE algorithm obtains better results, but also it converges much faster.

Key words: stochastic programming model, differential evolution algorithm, discrete differential evolution algorithm, vehicle routing problems(VRP)