物流配送路径优化研究和设计.docVIP

物流配送路径优化研究和设计 　　摘 要：物流配送路径优化问题复杂度高，具有随机性，而且多用户配送路径的选择更为复杂，难以抉择。研究的对象是一个货物配送中心对应于多个客户点，为解决物流配送路径优化问题，采用蚁群算法进行路径优化，并对物流配送路径进行模拟。 　　关键词：物流配送；路径优化；蚁群算法 　　中图分类号：G642 文献标识码：A 　　1 引言（Introduction） 　　物流配送在日常的生活里是非常常见的，因为它是由于社会分工深化和社会化大生产而产生的，物流涉及企业的生产与客户的消费，是现代社会赖以存在的基本经济活动之一。在现代社会中，物流，信息的传播与流动，商品流通称为三大经济支柱，物流管理系统化、合理化产生巨大的经济价值，基于此，物流被认为是 “第三利润源泉”[1]。 　　目前物流产业两个主要的发展的方向：①物流配送中资金的利用减少。②服务质量的提高。对应于物流发展方向，物流配送中资金的使用主要是两个方面：一是早期的投资，如仓库或者配送中心的建设费用；二是对货物的管理和配送产生的成本。由此看出，货物配送的最初理念就是在满足一定客户的需求下，进行配送成本的最小化，实现企业利润的最大化。 　　现在物流配送最关键的问题就是如何利用现有的一些技术来降低物流运输的成本，其中最关键的一个环节就是如何选择最优的物流配送路径，来达到运输成本最低的目的[2]。优化的物流配送路径包括很多，比如合理规划车辆的配送途径，增加货物配送车辆的装载率等，当企业在现实经营活动中成功的实现了这些措施时，就会大大节约运输时间和成本，最大化的实现企业的经济利润。 　　2 主要的物流配送路径优化求解算法（Algorithm 　　of logistics distribution path optimization） 　　物流配送中的车辆调度问题，求解的方法较多，大致分为两大类：精确算法和启发式算法。精确算法是指能够求出最优解的算法，主要包括：动态规划法、割平面法和分枝定界法等。因为精确算法的信息处理量大、数据分析量大，在实际中不常用。 　　主要的物流配送路径优化求解算法有， 禁忌搜索算法、模拟退火算法、蚁群算法。 　　1986年，Glover提出了禁忌搜寻法（Tbau Search，简称 TS），该算法扩展了对局部领域的搜索，也是全局逐步寻优的一种方法，更是对人类智力过程的一种模拟。TS 算法在许多领域都取得了很大的成功，比如生产调度、电路设计、网络等领域。模拟退火算法是启发式的随机优化方法的一种，是一种比较通用的而且在启发式优化方法中也比较成熟的优化方法。蚁群算法属于随机搜索算法，该方法利用蚁群搜寻食物的过程与旅行商问题（TSP）之间的相似性，人为模拟蚂蚁搜寻食物的过程（即通过个体之间的信息交流与相互协作最终找到从蚁穴到食物源的最短路径）来求解TSP[3]。 　　3 物流配送路径优化设计（Path optimization design 　　of logistics distribution） 　　蚁群算法具有通用性和鲁棒性，是基于总体优化的方法，在解决旅行商问题（TSP）、作业安排调度问题（JSP）、二次分配问题（QAP）等组合优化问题上具有一定的合理性，故采用此算法。 　　设定车辆代表蚂蚁，首先第一个车辆从某个配送点出发，选择下一个配送点，然后移动到被选择配送点，最后返回到最开始的配送点，则第一个车辆的配送任务完成。然后第二个车辆按照第一个车辆的方法进行配送。所有车辆依次配送完成后，保存当前最优路径，更新环境信息素。然后所有车辆再模拟一次货物的配送，配送完后再更新环境信息素。如此循环进行，直到达到设定的配送次数，输出最后的最优路径。 　　为了具体形象地描述模型，画出其配送示意图，假设有6个货物配送点，这6个货物配送点之间互通互达，车辆从货物配送点A出发，在剩下的5个货物配送点之间选择一个货物配送点作为下一个目标点，以此类推直到车辆完成货物配送后回到A，在此期间，车辆所走的最短的路线就是当前最优的配送路线。 　　利用面向对象语言建立一个简单的二位数组JLSZ用来记录这六个配送点之间的距离，数据可以用测量工具在地图上测量得到，把测量得到的数据再乘以地图缩放比例即可得到现实的距离。 　　这六个点测量得到的具体数据如表1，即二维数据JLSZ表。 　　利用面向对象语言建立一个简单的二位数组XXSSZ用来记录这六个配送点之间的环境信息素，刚开始的时候没有车辆还没有进行配送，所以这6个货物配送点之间的信息素的值是相同的，假设6个货物配送点之间初始信息素值为2。车辆随机选择下一个货物配送点，以此类推，不停的选择移动，直到把剩下的5个配送点全部遍历过后返回起配送点A才结束。 　　先假设第一个车辆的大概配送路线为：