基于gis和禁忌搜索集成技术的农产品物流配送路径优化

《基于gis和禁忌搜索集成技术的农产品物流配送路径优化》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、万方数据第41卷第10期2011年5月数学的实践与认识MATHEMATICSINPRACTICEANDTHEORYV01．41，No．10May，201l基于GIS和禁忌搜索集成技术的农产品物流配送路径优化邱荣祖-，钟聪儿-，修晓虎。(1．福建农林大学交通学院，福建福州350002)(2．福建省地质遥感中心，福建福州350002)摘要：分析农产品物流配送模式，对带时间窗的车辆路径问题进行描述，建立有时限的配送路径优化模型，应用GIS与禁忌搜索算法集成技术求解该模型，开发农产品物流配送路径优化系统，并以晋安区农产品物流配送基础数据为范例，进行系统的初步应用研究．关键词：农产品物流配送；路

2、径优化；地理信息系统；禁忌搜索算法；集成技术车辆路径问题(VehicleRoutingProblem，VRP)是组合优化领域的热点问题．主要是结合实际需求，围绕VRP的不同分类，分别从模型、算法以及系统实现进行研究[1--5】．农产品物流配送路径优化属于车辆路径问题范畴，是农产品物流配送系统优化决策的核心问题之一．由于农产品物流配送受到农产品的供需分布、供需情况、道路网络以及自然条件等因素的影响，再加上农产品配送自身批量小、多批次、易腐烂变质等特性，农产品物流配送路径优化是一个受空间和时间限制的NP难题．本文针对研究对象的特殊性，讨论了带时间窗的农产品物流配送路径优化问题，研究将GIS

3、与禁忌搜索集成技术应用于该问题的求解．GIS技术的引入，除了能够方便地对配送过程中的相关信息进行处理和直观表达，还能通过其强大的空间与网络分析功能，获得各个网点之间的最短路径，在此基础上，利用禁忌搜索算法强健的搜索能力，在VB环境中开发基于该算法的ActiveXDLL应用程序，实现农产品物流配送路径的合理优化．对于在保持准时、准确配送的要求下，有效提高农产品物流配送效率和服务质量，降低配送成本，具有理论价值和实际意义．1农产品物流配送路径优化模型针对农产品物流配送过程中农产品品种多、数量少、批次多、交通情况复杂，容易腐烂变质，销售时间段比较固定等特点，建立用多台车辆向多个客户进行农产品

4、物流配送的路径收稿日期：2010-01—26’资助项目：福建省教育厅高校专项(闽教科【2010133号)万方数据146数学的实践与认识41卷优化模型．假设：配送中心的位置，客户的位置和需求量，每台车辆的载重量，车辆一次配送的最大行驶距离为已知，配送中心供应的农产品能够满足所有客户的需求．要求合理安排车辆配送路线，使配送里程最短，并满足以下条件[6】=①每条配送路径上各客户的需求量之和不超过车辆的载重量；②每条配送路径的长度不超过车辆一次配送的最大行驶距离；③每个客户的需求必须满足，且只能由一台车辆进行配送；④每项配送任务必须在要求的特定时间范围内将农产品送到客户手中．因此，带时间窗的农

5、产品物流配送路径优化模型如下：1)，r％(i))+d(rk(n(南))，r％(o))sign(佗(尼)))(1)s．t．∑口Mt)]≤Qk凡(知)∑(f(rk(i一1)，仉(i))+d(r％(n(七)),rk(O))sign(n(k))≤DkRklnRk2=咖(七1≠k2)sig懈n))=R巍型Sk(i)=研k({-1)+trk(t—1)+trk(t—1)rk(t)0k(t)=max{a，k(。)一Sr^(t)，o)式中：H一配送中心个数；L一客户个数，每一客户只能由一台车辆服务；K配送车辆数；Qk～每台车辆的载重量，t，(k=1，2，⋯，玩)；Dk一每台车辆一次配送的最大行驶距离，k

6、in；d(i，歹)配送中心服务的客户i到J的运距，km，(i，J=z，2，⋯，L)；n(k)第k台车辆配送的客户总数，n(k)=0表示未使用第七台车辆；吼一第k条路径上的客户集合；他(i)一客户rk(i)在第k台车辆配送路径中的顺序为i(不包括配送中心)；令rk(0)=0表示配送中心；(f(n(0)，i)一配送中心到第i个客户的距离，km，(i=f，2，⋯，L)；d(i，％(o))一第i个客户到配送中心的距离，km，(i=1，2，⋯，L)；q[rk(i)】_配送中心中的第k辆车配送的客户rk(i)的需求量，t；S。(i)配送中心中的第k辆车到达配送客户r％(t)的时刻；trk(。)一配

7、送中心中的第惫辆车在客户_rk(i)的等待时间，^；t，。(卜1)，。({)一配送中心中的第k辆车从客户rk(i～1)‘到客户71k(i)的行驶时间，h客户rk(i)的时间窗为[o，．。(i)，k。(i)]．施m州∑嘲K∑脚Ⅱ万方数据邱荣祖，等：基于GIS和禁忌搜索集成技术的农产品物流配送路径优化1472GIS与禁忌搜索算法集成技术2．1禁忌搜索算法禁忌搜索算法是解决组合优化问题的一种优化方法，也是局部搜索算法的拓广本文主要通过以下算法策略[7