朱 伟，徐克林，佀占华，周 娜

（同济大学 机械工程学院，上海201804）

对配装配载及配送路线优化问题的研究一直是运输组织以及运筹学关注的重点，二者既相互影响，又相互制约.为提高配送系统运作效率及服务水平、进一步降低成本，必须从系统化、集成化的角度出发，将配装配载与运输两大功能进行整合［1］.基于以上思路，本文研究并建立了单车辆配装运输决策模型 （decision-making model for single vehicle loading-transportation，SLTD）.

SLTD 研究是典型的组合优化领域的非确定性多项式难题（NP-Hard）［2］，传统的求解方法一般是优化或启发式算法，如Clarke和Wright提出的节约算法［3］，Gillett和Miller提 出 的Sweep算 法［4］，Lin提出的r-opt（r=2，3，…；r指改换的边数）算法［5］，Norback和Love研究的几何图解算法［6］，Landrieu等运用的Tabu算法［7］等，但这些算法随结点数的增加会出现组合爆炸现象.

遗传算法（genetic algorithm，GA）最早由美国Michigan大学的Holland教授于1975年提出，它是受生物进化规律启迪的概率搜索方法［8］，极强的鲁棒性和内在的并行计算机制使它不仅在旅行商问题、背包问题、图分割问题等组合优化问题中取得了很多成果［9-10］，而且在配装配载和运输问题中也有广泛应用［11-12］，但遗传算法在SLTD 中的应用尚不多见.本文用VC++6.0语言实现了求解SLTD 模型的遗传算法，实例计算表明了算法及模型的有效性.

1 SLTD 问题定义及模型建立

1.1 SLTD问题定义

SLTD 问题可定义为：有l个客户点，配送中心服务它们的配送需求，已知运输车辆的载重量限制为G，容积限制为V，以总配送成本最低和车载利用率最高为目标函数，在一定的约束条件下，确定满足配送要求的最合适的车辆数m和最佳的车辆行程线路.本文研究SLTD 模型基于如下假设：配送中心到各需求点的距离及需求点间的距离已知；……