带装卸顺序约束的装载配送联合优化算法研究

互斥产品(如液体、危险化学品等)不能混装到同一个容器中,物流企业通常使用多隔舱运输车为顾客配送多种互斥产品,合理确定装载与配送路径是提高配送效率、降低配送成本的重要手段.本文考虑互斥产品的装卸顺序约束、在途运输时间约束等,构建了以配送成本最小化为目标的互斥产品装载配送联合优化模型,设计了求解模型的改进遗传算法,算法采用蜂王进化和基于概率的边重构交叉运算,有效提高了寻优能力.本文利用Augerat提供的车辆路径问题标准测试集构造算例测试算法的运行时间和求解效果.结果显示,改进遗传算法的求解效果明显优于经典遗传算法.对于小规模算例,改进的遗传算法可以得到精确最优解,对于中等规模和不超过101个顾客点的大规模算例,改进的遗传算法可以在130秒内得到近似最优解.本文的创新点在于构建了一类新的车辆路径扩展问题的数学模型并设计了求解模型的快速有效算法,为物流企业制定多类型互斥产品配送计划提供了理论依据和算法支持.

Study on joint optimization algorithm for loading and distribution with loading and unloading sequence constraints

Mutually exclusive products (such as liquids, hazardous chemicals, etc.) cannot be mixed into the same container. Logistics companies usually use multi-compartment trucks to deliver mutually exclusive products to customers. The loading and vehicle routing strategies are the key issues to determine the distribution efficiency and distribution costs. Considering the constraints of loading and unloading sequence and transportation time of mutually exclusive products, a joint optimization model of loading and distribution is constructed to minimize the distribution cost. This paper designs an improved genetic algorithm for solving the model, using the queen evolution and the edge reconstruction crossover operations based on probability to lift the ability of finding the optimal solution. Then we construct the testing examples based on the vehicle routing problem benchmark provided by Augerat to verify the running time and solving efficient of genetic algorithm. The simulation results show that, the solutions obtained by improved genetic algorithm are better than those of classical genetic algorithm, for small-scale examples, the improved genetic algorithm can obtains global optimal solution; for the medium-sized or large size examples with no more than 101 customers, the approximate optimal solution can be obtained in 130 seconds using genetic algorithm. The innovation of this paper lies in the establishment of a mathematical model for a new expended vehicle routing problem and the design of a fast and effective algorithm for solving the model. The mathematical model and algorithm of this paper provide a theoretical basis and algorithmic support for logistics companies to draw up distribution schedule of mutually exclusive products.