基于遗传算法的物流配送路径优化问题研究.doc

基于遗传算法的物流配送路径优化问题研究.doc基于遗传算法的物流配送路径优化问题研究郎茂祥(北方交通大学交通运输学院,北京100044)摘要:论文在建立物流配送路径优化问题的数学模型的基础上,构造了求解该问题的遗传算法,并进行了实验计算。计算结果表明,用遗传算法进行物流配送路径优化,可以方便有效地求得问题的最优解或近似最优解。关键词:物流配送;遗传算法;icAlgorithmLANGMao-xiang(SchoolofTrafficandTransportation»NorthernJiaotongUniversity,Beijing100044,China)Abstract;Onthebasisofestablishingtheoptimizingmodelonphysicaldistributionroutingproblem,icalgorithmforsolvingthisproblem,:physicaldistribution;icalgorithm;optimizing1引言随着市场经济的发展和物流技术专业化水平的提高,物流配送业得到了迅猛发展。物流配送是指按用户的订货要求,在配送屮心进行分货、配货,并将配好的货物及时送交收货人。在物流配送业务屮,存在许多优化决策问题,木文讨论其屮的物流配送路径优化问题,即通过制定合理的配送路径,快速而经济地将货物送达用户手屮。配送路径的选择是否合理,对加快配送速度、提高服务质量、降低配送成木及增加经济效益都有较大影响。研究表明,配送路径优化问题是一个NP难题,只有在需求点和路段较少时,才能求得精确解。因此,用启发式算法求解该问题就成为人们研究的一个重要方向,并出现了多种启发式算法,如Clarke和Wright提岀的节约法,Gillett和Miller提出的扫描法⑴等,虽然这些算法为求解配送路径优化问题提供了有效的方法,但也存在一定的问题,如节约法虽然具有运算速度快的优点,但也有纟R合点零乱、边缘点难以组合的问题,扫描法为非渐进优化等。如何针对物流配送路径优化问题的特点,构造运算简单、寻优性能优良的启发式算法,是一个值得深入研究的课题。遗传算法的出现为求解物流配送路径优化问题提供了新的工具,[叫它是一种借鉴生物界自然选择和白然遗传机制的随机化搜索方法。由于遗传算法采用随机选择,对搜索空间无特殊要求,无需求导,具有运算简单、收敛速度快等优点,尤其适用于处理传统搜索方法难于解决的复杂和非线性的问题,目前已广泛应用于组合优化、机器学****白适应控制等领域。木文针对物流配送路径优化问题的特点,构造了求解该问题的遗传算法,通过实验计算,得到了较好的结果。2物流配送路径优化问题的数学模型物流配送路径优化问题可以描述为:从配送屮心(或称物流据点)用多辆汽车向多个需求点(或称顾客)送货,每个需求点的位置和需求量一定,每辆汽车的载重量一定,要求合理安排汽车路线,使总运距最短,并满足以下条件:(1)每条配送路径上各需求点的需求量Z和不超过汽车载重量;(2)每条配送路径的长度不超过汽车一次配送的最大行驶距离;(3)每个需求点的需求必须满足,且只能由一辆汽车送货。木文借鉴文献[3]建立的车辆路径问题的数学模型