文档介绍：浅析物流配送最短路径选择方法■■蚁群算法翁凌云浙江工业大学计算机学院、网络工程,浙江杭州310000摘要:据中研普华<2013-2017年物流行业全景调研与投资策略研究咨询报告》显示,2012年我国物流业实现平稳适度增长,但物流要素成本也在全面上涨,物流企业生存空间进一步压缩运输服务作为物流组成中的重要环节,是降低运输成本、提高运输质量和效率成为加快物流发展的有效途径,亦是运输服务优化中的核心问题。它通过对货物的运输线路进行优化,在满足客户需求的前提下,尽量以最低的运输成本将货物送达目的地。在过去几十年间,车辆路径问题(VehicleRoutingProblem,简称VRP)得到了广泛的关注和研究,并取得了丰富的研究成果。本文针对这类问题的构成、分类以及求解算法中的蚊群算法在这方面的运用等进行了归纳和概括。关键词:物流;最短路径;算法;引言美国物流管理学会(CouncilofLogisticsManagement,CLM)对物流所作的定义为:“为符合顾客的需要,对原料、制造过程中的存货与制成品以及相关信息,从其起运点至最终消费点之间,做出的追求效率与成本效果的计划、执行与控制过程。”而有关资料显示,物流配送过程(包含仓储、分拣、运输等)的成本构成中,运输成本占到52%之多。因此,如何在满足客户适当满意度的前提下,将配送的运输成本合理地降低,成为一个紧迫而重要的研究课题,车辆路径问题正是基于这一需求而产生的。车辆路径问题的定义车辆路线问题(VRP)最早是由Dantzig和Ramser于1959年首次提出,它是指一定数量的客户,备自有不同数量的货物需求,配送中心1何客户提供货物,由一个车队负责分送货物,组织适当的行车路线,目标是使得客户的需求得到满足,并能在一定的约束下,达到诸如路程最短、成本最小、耗费时间最少等bl的⑵。车辆路线问题自1959年提出以来,一直是网络优化问题中最基本的问题之一,由于其应用的广泛性和经济上的重大价值,一直受到国内外学者的广泛关注。设有一场站(depot),共有M辆货车,车辆容量为Q,有N位顾客(customer),位顾客有其需求量D。车辆从场站出发对客户进行配送服务最后返IE场站,要求所有顾客都被配送,每位顾客一次配送完成,且不能违反车辆容量的限制,目的是所有车辆路线的总距离最小。因此研究车辆的路径问题,就是要研究如何安排运输车辆的行驶路线,使运输车辆依照最短的行驶路径或最短的时间费用,依次服务于每个客户后返I可起点,总的运输成木实现最小。车辆路线问题可以描述如下(如图1):场站物流配送路径问题,实际上是旅行商(TravelingSales—manProblem,TSP)的问题,对TSP的问题描述如下:一个货郎要走访N个城市,每个城市必须经过一次且只能经过一次,最后|口1到出发的城市,就算是完成了一次旅行,找到一条最短的路径。其相应数学描述如下:设有一城市集合C=(cpc2,c3c「},每对城市Cj,GWC间的距离为d(Cj,Cj)cZ+。求一条经过C中每个城市正好一次的最短路径。车辆路径问题(VRP)的研究方法主要有精确优化算法、启发式优化算法和仿生优化算法三大类别'七仿生优化算法是近几年来在求解组合优化问题方面发展较快的一个方向。其中蚁群算法是一神对日然界中生物觅食行为进行计算机模拟的算法,该算法具有并行性、突现性、进化