工业工程

工业工程 ›› 2011, Vol. 14 ›› Issue (5): 71-74.

• 专题论述 • 上一篇    下一篇

三维装载约束的车辆路径问题的模拟退火算法

  

  1. 1.华南理工大学 工商管理学院，广东 广州 510641；2.广东外语外贸大学 思科信息学院，广东 广州 510006
  • 出版日期:2011-10-31 发布日期:2011-11-11
  • 作者简介:彭碧涛（1978-），男，湖北省人，讲师，博士研究生，主要研究方向为车辆路径问题、人工智能.
  • 基金资助:

    国家自然科学基金资助项目（70971041）；教育部人文社科一般项目（青年项目）（10YJC790339）；2010年度广东外语外贸大学青年项目; 广东省高校人文社科基地项目（08JDXM63003）

Simulated Annealing Algorithm for Vehicle Routing Problem with Three Dimensional Loading Constraints

  1. 1.School of Business Administration, South China University of Technology, Guangzhou 510641, China； 2.Cisco School of Informatics, Guangdong University of Foreign Studies, Guangzhou 510006, China
  • Online:2011-10-31 Published:2011-11-11

摘要： 传统的车辆路径问题只考虑物品装载的质量属性约束，而忽略其他装载属性约束。针对这种情况，研究了三维装载约束的车辆路径问题，提出了三维装载的处理算法，基于模拟退火算法设计了一种两阶段启发式算法进行求解:第1阶段通过启发式算法得到初始解;第2阶段通过模拟退火算法对初始解进行改进，构造了测试集对结果进行验证。实验结果显示该算法是能够有效的求解该问题。

关键词: 三维装载, 车辆路径问题, 模拟退火

Abstract: In the classical vehicle routing problem, it considers the goods weight constraint only，but ignores other loading constraints, such as the loading space constraint. In this paper, the vehicle routing problem with threedimensional loading constraint taken into account is addressed. A heuristic is proposed for goods loading such that the three dimensional loading constraint is satisfied and optimized. Then, based on the heuristic, a simulated annealing algorithm is presented to solve the problem. A number of benchmark problems are used to test the proposed method. Results show the algorithm is effective.

Key words: three-dimensionalloading, vehicle routing problem, simulated annealing