Journal of Computer Applications ›› 2018, Vol. 38 ›› Issue (12): 3618-3624.DOI: 10.11772/j.issn.1001-9081.2018051085

Previous Articles     Next Articles

Optimization model of green multi-type vehicles routing problem

HE Dongdong, LI Yinzhen   

  1. School of Traffic and Transportation, Lanzhou Jiaotong University, Lanzhou Gansu 730070, China
  • Received:2018-05-28 Revised:2018-07-10 Online:2018-12-10 Published:2018-12-15
  • Contact: 李引珍


何东东, 李引珍   

  1. 兰州交通大学 交通运输学院, 兰州 730070
  • 通讯作者: 李引珍
  • 作者简介:何东东(1992-),男,四川达州人,硕士研究生,主要研究方向:交通运输规划与管理、网络优化;李引珍(1963-),男,甘肃天水人,教授,博士,主要研究方向:运输系统分析与决策。

Abstract: In order to reduce the waste gas pollution generated by vehicles in the process of logistics distribution, on the basis of traditional Vehicle Routing Problem with Time Windows (VRPTW) model, an approximate calculation method for fuel consumption and carbon emission was introduced from the perspective of energy saving and emission reduction, then a Green Multi-type Vehicles Routing Problem with Time Windows (G-MVRPTW) model was established. The minimum total cost was taken as an optimization objective to find environment-friendly green paths, and an improved tabu search algorithm was designed to solve the problem. When the initial solution and the neighborhood solution were generated, the order of customer sequence in the subpath was set according to the ascending order of the latest service time and the time window size of each customer point. At the same time, through three indexes of the minimum subpath, the total cost of subpaths and the overload, the evaluation function of solution was improved, and a mechanism of reducing the possibility of precocious maturing was adopted. Finally, the effectiveness and feasibility of the proposed model and algorithm were verified by numerical experiments. The experimental results show that, the ton-kilometer index can better measure the fuel consumption and carbon emission cost, and it is a new trend for new energy vehicles to enter the transportation market. It can provide decision support and methodological guidance for low-carbon transportation and management.

Key words: vehicle routing problem, energy consumption, carbon emission, tabu search algorithm, green and low carbon

摘要: 为降低物流配送过程中车辆产生的废气污染,在传统带时间窗车辆路径问题(VRPTW)的基础上,从节能减排的角度出发,引入了油耗和碳排放量的近似计算方法,建立了带时间窗的多车型绿色车辆路径问题模型(G-MVRPTW)。该模型将总成本最小作为优化目标来寻找环境友好型绿色路径,同时设计了改进的禁忌搜索算法求解该问题。该算法在初始解和邻域解的生成时,规定子路径内客户序号顺序按照各个客户点最迟开始服务时间和时间窗大小升序排列。同时,通过最少子路径、子路径总费用和超载量三个指标,改进了解的评价函数,并采用了减少早熟可能性的机制。最后,通过数值实验验证了所提模型和算法的有效性和可行性。实验结果表明,吨公里指标能更好衡量油耗和碳排放成本,新能源车投入运输市场将是新的趋势,可为低碳运输及管理提供决策支持和方法指导。

关键词: 车辆路径问题, 能耗, 碳排放, 禁忌搜索算法, 绿色低碳

CLC Number: