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

《基于遗传算法的物流配送路径优化问题研究》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、第15卷第3期中国公路学报Vol.15No.32002年7月ChinaJournalofHighwayandTransportJuly20023Y3t}$:1001-7372(2002)03-0076-04基于遗传算法的物流配送路径优化问题研究郎茂祥(北方交通大学交通运翰学院，北京100044)摘要:在建立物流配送路径优化问题数学模型的基础上，构造了求解该问题的遗传葬法，并进行了实脸计算。计算结果表明，用遗传算法进行物流配送路径优化，可以方便有效地求得问题的最优解或近似最优解。关键词:物流配送;遗传算法;优化中图分类号:U492.3文献

2、标识码,AStudyoftheoptimizingofphysicaldistributionroutingproblembasedongeneticalgorithmLANGMao-xiang(SchoolofTrafficandTransportation,NorthernJiaotongUniversity,Beijing100044,China)Abstract;Onthebasisofestablishingtheoptimizingmodelonphysicaldistributionroutingproblem,thisp

3、aperpresentsageneticalgorithmforsolvingthisproblem,andmakessomeexperimentalcalculations.Theexperimentalcalculationsresultsdemonstratethattheoptimalornearlyoptimalsolutionstothephysicaldistributionroutingproblemcanbeeasilyobtainedbyusinggeneticalgorithm.Keywords;physicald

4、istribution;geneticalgorithm;optimizing和MILLER提出的扫描法[n:等，虽然这些算法为求0引言解配送路径优化问题提供了有效的方法，但也存在随着市场经济的发展和物流技术专业化水平的一定的问题，如节约法虽然具有运算速度快的优点，提高，物流配送业得到了迅猛发展。物流配送是指按但也有组合点零乱、边缘点难以组合的问题，扫描法用户的订货要求，在配送中心进行分货、配货，并将为非渐进优化等。如何针对物流配送路径优化问题配好的货物及时送交收货人在物流配送业务中，存的特点，构造运算简单、寻优性能优良的启发式算在许多

5、优化决策问题，笔者讨论其中的物流配送路法，是一个值得深人研究的课题。径优化问题，即通过制定合理的配送路径，快速而经遗传算法的出现为求解物流配送路径优化问题济地将货物送达用户手中。配送路径的选择是否合提供了新的工具，该算法是由美国的H()L工.-ANDJ理，对加快配送速度、提高服务质量、降低配送成本教授于1975年提出的U]，它是一种借鉴生物界自然及增加经济效益都有较大影响。选择和自然遗传机制的随机化搜索方法。由于遗传研究表明，配送路径优化问题是一个NP难题，算法采用随机选择，对搜索空间无特殊要求，无需求只有在需求点和路段较少时，才能求得

6、精确解。因导，具有运算简单、收敛速度快等优点，尤其适用于此，用启发式算法求解该问题就成为人们研究的一处理传统搜索方法难于解决的复杂和非线性的问个重要方向，并出现了多种启发式算法，如题，目前已广泛应用于组合优化、机器学习、自适应CLARKE和WRIGHT提出的节约法,GILLETT控制等领域。笔者针对物流配送路径优让问颇的特收摘日期2001-08-23作者简介郎茂洋自969-).男，山东高唐人，北方交通大学副教授.1学博士研究生第3期郊茂祥:基于遗传算法的物流配送路径优化问题研究点，构造了求解该问题的遗传算法，通过实验计算，量;式((3)

7、保证每条配送路径的长度不超过汽车一次得到了较好的结果。配送的最大行驶距离;式(4)表明每条路径上的需求点数不超过总需求点数;式((5)表明每个需求点都得1物流配送路径优化问题的数学模型到配送服务;式(6)为每条路径的需求点的组成;式物流配送路径优化问题可以描述为:从配送中(7)限制每个需求点仅能由一辆汽车送货;式((8)为心(物流据点)用多辆汽车向多个需求点(顾客)送当第k辆汽车服务的客户数)1时，说明该辆汽车货，每个需求点的位置和需求量一定，每辆汽车的载参加了配送，则取、馆n(n,)=1，当第k辆汽车服务重量一定，要求合理安排汽车路线

8、，使总运距最短，的客户数<1时，表示未使用该辆汽车，因此取并满足以下条件:sign(nk)=().(1)每条配送路径上各需求点的需求量之和不z物流配送路径优化问题的遗传算法超过汽车载重量;(2)每条配送路径