基于标签算法的异车型混合集送多属性车辆路径问题研究

A Multi-Label Heuristic Algorithm for Multi-Vehicle Routing Problem

文章对异车型混合集送的辆路径问题(Vehicle Routing Problem with heterogeneous fleet,backhaul and mixed-load,VRPHBM)进行研究,提出了一种基于多属性标签的蚁群系统算法(Multi-Label based Ant Colony System简称MLACS)。该算法利用面向对象理念,分别对客户、车辆及其行驶路径构建多属性标签,再通过蚁群算法的搜索规则对客户和车辆标签进行匹配,从而得出满意的车辆行驶路径。通过Solomon标准及其扩展算例和实际案例的验证表明,MLACS具有快速、灵活和稳定等特点,能够很好地解决VRPTW、VRPHBM以及多限制条件的实际应用问题。与本文列出的研究同类型问题文献的其他几种算法相比,MLACS算法在运算时间以及计算结果上明显具有优势,是求解该类问题的有效算法。

When solving the vehicle routing problem （VRP）, a variety of different operational characteristics and constraints, such as vehicle types, backhaul trips and other working regulations, must be considered. These constraints are also called attributes. With these attributes, many extended problems can be generated from the traditional vehicle routing problem, and these problems become much more complicated and difficult to be solved. In this paper, we consider a class of vehicle routing problems with heterogeneous fleet, backhauls, mixed load and hard-time windows （VRPHBM）. The research is motivated by the scenario that different postal shuttles transport outbound mails from and carry inbound mails back to the mail processing center every day. This study aims at achieving a solution with fewer vehicles, less time and lower cost. To handle this problem, we propose a label based ant colony system algorithm （MLACS） which takes advantages of both label matching approach and ant colony system algorithm. Due to the flexibility of labels, the most important contribution of MLACS is that we can tackle different operational constraints easily by making some adaptations to labels and label matching rules. Other characteristics that MLACS inherit from multiple ant colony system are robust and good at achieving global optimal solution. Firstly, we describe the problem of VRPHBM, establish the integer programming formulations of the object and present various constraints. After defining various labels of demands, vehicles and routes with object-oriented concepts, the label generation and matching rules are illustrated accordingly. Secondly, we describe how the MLACS works. At first, we construct an initial solution with the nearest neighborhood algorithm, and improve it with ant colony system algorithm （ACS） in both directions of tours minimization and total route length minimization. In the end, we conduct three experiments to test the effectiveness and efficiency of our algorithm. From the experimental results of Solomon Benchmarks R1 problems, we find out that the solutions of MLACS are almost the same as those of/P-Opt. However, it costs much less computational time. In the extended data, we can see that MLACS produces solutions with shorter route length and fewer vehicles than those of comparison algorithms. In the real case, we find out that MLACS achieves 9% of total cost reduction and uses one less vehicle. This means that the MLACS algorithm is effective in real world application. The experimental results show that our algorithm is effective and efficient. Due to the flexibility that MLACS inherited from multi-attribute labels and efficiency from ACS, we believe that MLACS can be extended to handle other routing problems.