求解异车型同时集送问题的多属性标签算法

A heuristic algorithm for vehicle routing problem with heterogeneous fleet,simultaneous pickup and delivery

针对实际运输中顾客对不同车型、同时集送货物的多样化需求,文章建立了异车型同时集送车辆路径模型(vehicle routing problem with heterogeneous fleet,simultaneouspickup and delivery,VRPHSPD),并构建了基于多属性标签的蚁群系统算法(multi-label based ant colony system,MLACS)进行求解.该算法利用面向对象理念,分别对客户、车辆及其行驶路径构建多属性标签,首先用近邻法生成初始路径,再通过蚁群算法的搜索规则对客户和车辆标签进行匹配,从而得优化的结果.通过公开算例、实际应用案例的验证表明,MLACS算法能成功求解VRPHSPD问题,具有较高的求解质量、运算效率以及实际应用意义.

In this paper, we propose a new algorithm multi-label based ant colony system （MLACS） algorithm to address the vehicle routing problem with heterogeneous fleet, simultaneous pickup and delivery （VRPHSPD） problem which meet often in the real word. Leveraging the object-oriented principle, we build multi-attribute labels for various customers （demands）, vehicles and routes. And then, we initialize the solution through nearest neighbor heuristic approach and minimize the number of vehicles required and total travel length by MLACS. To evaluate the efficiency and effectiveness of MLACS, we compare it with other optimization algorithms using benchmark problems and practical problem. Our results show that the MLACS algorithm has significant advantages in achieving the objectives as well as computing time. In addition, a numerical simulation using the actual data shows that MLACS is also good at solving the real world problem.