装卸混合车辆路径问题的模型及其模拟退火算法.docVIP

装卸混合车辆路径问题的模型及其模拟退火算法研究 郎茂祥 （北京交通大学 交通运输学院，北京 100044） 摘 要：论文研究提出了更具一般性的装卸混合车辆路径问题，并建立了该问题的基于直观描述的数学模型。论文还通过设计一种新的解的表示方法构造了求解该问题的模拟退火算法，并进行了实验计算。计算结果表明，用本文设计的模拟退火算法求解装卸混合车辆路径问题，不仅可以取得很好的计算结果，而且算法的计算效率较高，收敛速度较快，计算结果也较稳定。论文还通过对双向配送策略的计算结果与单向配送策略的计算结果的比较，说明了采用双向配送策略求解装卸混合车辆路径问题对于配送企业节省配送车辆、减少配送里程，从而降低配送成本、提高经济效益的重要意义。 关键词：装卸混合车辆路径问题；模拟退火算法 Study on the Model and Simulated Annealing Algorithm for Vehicle Routing Problem with Backhauls LANG Mao-xiang （School of Traffic and Transportation，Beijing Jiaotong University，Beijing 100044，China） Abstract：A vehicle routing problem with backhauls which is more general was presented in this paper. On the basis of modeling the vehicle routing problem with backhauls based on natural description, this paper builds a simulated annealing algorithm for the problem by presenting a new solution indicating method and makes some experimental computations. The computational results demonstrates that the high quality solutions to the vehicle routing problem with backhauls can be obtained by using the new simulated annealing algorithm and the new algorithm is also efficient and robust. Through comparing the results of the two-direction distribution tactics with those of the one-direction distribution tactics in solving the problem, this paper also illustrates the advantages of using two-direction distribution tactics to solve the vehicle routing problem with backhauls for physical distribution enterprises in saving distribution vehicles, reducing logistics cost and raising economic benefits. Keywords：; simulated annealing algorithm 0 引言 车辆路径问题（Vehicle Routing Problem，VRP）是当前运筹学与组合优化领域的前沿与热点问题。在现实生产和生活中，物流配送车辆调度问题、邮政投递问题、公共汽车调度问题、电力调度问题、管道铺设问题、计算机网络拓扑设计问题等都可以抽象为车辆路径问题。因此，研究车辆路径问题具有重要的理论和现实意义。 为了使问题易于理解，本文将以物流配送为背景研究车辆路径问题，即研究物流配送中的车辆路径问题。 现有文献研究的车辆路径问题多为单向车辆路径问题，包括从散货型物流中心向客户送货的纯送货问题和将货物从客户取到集货型物流中心的纯取货问题。除了散货型和集货型物流中心外，现实中还有许多集散型的物流中心，如铁路货场、公路中转站及港口码头等。对于这类集散型物流中心，在制定配送方案时，既要考虑将客户需要的货物从物流中心送到各个客户，又要考虑将客户生产或供应的货物从客户取到物流中心，本文称上述问题为装卸混合车辆路径问题。对