考虑城市路网结构的物流配送优化方法
2014-04-18周瑞华
周瑞华
(1.深圳市凯立德科技股份有限公司,广东 深圳 518042)
考虑城市路网结构的物流配送优化方法
周瑞华1
(1.深圳市凯立德科技股份有限公司,广东 深圳 518042)
随着城市路网的建设与扩张,城市物流配送体系的构建变得更为复杂。对城市路网结构影响下的物流配送路线选择进行了研究,为物流企业在配送路线的选择与优化方面提供分析思路。实验证明,该方法在优化线路里程方面颇有效果。
路网结构;物流配送;蚁群算法
在城市物流配送中,城市道路网络是物流配送所依附的重要载体。伴随着我国城市道路网络的扩张与升级,物流配送网络变得更加复杂,如何选择切实有效的配送路线以降低物流配送成本成为物流活动中的首要问题。
传统的物流配送排单多是根据资深排单员的经验或者是地图上各配送点间的直线距离进行的[1],未能考虑道路的网络结构、路左还是路右等实际情况,这样的排单会给配送车辆在配送订单时带来诸多不便,造成多走回头路、绕远等情况。文章对城市路网结构的物流配送路线选择方法进行了优化,为物流企业在配送路线选择与优化方面提供分析思路。
1 城市路网结构分析
城市路网结构是由一定数量的城市道路按照一定方式组合而成的具有一定形态的网络结构。从纵向来看,对城市道路进行等级配置,就形成了城市道路网络的等级结构;从横向来看,对城市道路进行排列组合,并通过适当的方式进行衔接,就形成了城市道路网络的布局结构。因此,城市路网结构是一个综合性的概念,包括路网等级结构和路网布局结构,本文主要从城市路网布局结构来进行分析。
城市路网布局结构是城市的交通网络骨架,其形态主要有:方格式路网、环形放射式路网、自由式路网和混合式路网4种[2]。为了有效地描述城市路网布局,采用路网布局指标通过定量的方式来反映城市路网的布局结构。该指标体系中包含多个指标,其中对物流配送路径选择产生影响的指标有反映2点间实际距离大小的非直线系数指标和反映路网平均行程距离的可达性指标。
1)非直线系数指标。非直线系数指标是路网布局的重要评价指标之一,用来反映路网中2点之间的交通便捷程度[3]。非直线系数指标计算式如下:
式中,η为2点直接的非直线系数;F为2点之间的实际最短距离;为2点间的直线距离。
2)路网可达性指标。路网可达性是指在规划区域内某一点出发抵达任一目的地的行程距离、行程时间或费用的大小[4]。常用车辆的平均行程时间或距离表示路网的可达性,本文采用路网的平均行程距离来表示,假设路网的平均出行距离为D,其矩阵表达式为:
路网中某一节点的可达性,即某一点开始至其他各点的平均出行距离Di表示为:
式中,n为区域内的节点数目为矩阵D第i行元素之和。
路网可达性的值越大,代表路网的平均行驶距离越大,即路网中交通越不方便;反之,交通越便捷。
2 城市路网结构影响下的物流配送
2.1 建立模型
本文研究单配送中心无时间窗配送路线问题,具体描述如下:物流配送由1个配送中心、N个配送点组成,配送点不提出时间限制。送货的车辆从配送中心出发,依次给每一个配送点送货,完成最后一个配送点的配送任务后返回配送中心,目标是使得总配送里程最小。为了构造数学模型方便,将配送中心编号为0,各配送点编号为1,2,…,x,则该问题的数学模型如下:
考虑到路网布局对配送路径选择的影响,将与2点间距离有关的非直线系数加入模型中,改进可得到考虑路网布局的配送路线选择模型。
2.2 模型计算
本文采用蚁群算法来对物流配送路线选择问题进行优化求解。计算流程如下:
1)生成m个蚂蚁,每个蚂蚁对应的禁忌表设为空,并建立禁忌表指针。设定初始时刻t=0,初始迭代次数cycle=0。建立最短路径向量α及最短路径长度变量α为空设为一个很大的正数。将每一个蚂蚁随机放在要访问的n个配送点上。
2)每一只蚂蚁所处的配送点序号写入该蚂蚁禁忌表指针所指的格内,表明蚂蚁从该配送点出发,此时禁忌表指针移向禁忌表的下一格。
3)每一个蚂蚁按照路网中2点间可达性指标大小选出下一步要到达的配送点,并移动至该配送点。将该配送点的序号写入该蚂蚁禁忌表指针所指向的格内,指针再移向下一格。重复执行该步骤,直到蚂蚁遍历所有的配送点。
4)把各蚂蚁最后访问的配送点记录下来,计算各蚂蚁所走过的路径总长度Sk,并找出其中的最小值S,若把最小值对应的路径写入α中。
5)若cycle小于规定的迭代次数,各蚂蚁的禁忌表指针指向第一格,将上一轮最后遍历的配送点序号写入该蚂蚁禁忌表指针所指向的格内,指针移向下一格,转到步骤3)。若cycle等于规定迭代次数时结束该步骤。
2.3 实验结果
利用上述方法对武汉市某药品配送公司的20个配送订单进行了优化,并与人工排单结果进行比较。如表1所示,优化后物流配送路线较人工排单优化最大达18.77%,最小为6.08%,平均优化配送里程12.69%,优化效果明显。
表1 实验结果
3 结 语
传统的人工排单方式在物流配送中已难以满足物流企业高效、低成本的需求。文章利用蚁群算法结合城市路网结构对物流配送路线选择进行优化,可以在很大程度上降低物流成本,提高物流企业的生产管理水平。
[1] 高晓亮,伊俊敏,甘卫华.仓储与配送管理[M].北京:清华大学出版社,2006
[2] 钟石泉.物流配送车辆路径优化方法研究[D].天津:天津理工大学,2007
[3] 钱雪娟.城市路网结构评价方法探讨[J].交通科技与经济,2006,9(2):88-90
[4] 曾松,杨佩坤.城市路网结构的可达性评价[J].同济大学学报,2001,6(4):668-670
[5] 孙洪茹.城市物流配送体系及其路线优化的研究[D].青岛:山东科技大学,2005
[6] 吴静.改进的智能算法及其在物流运输优化中的应用[D].天津:天津理工大学,2008
[7] 郎茂样.基于遗传算法的物流配送路径优化问题研究[J].中国公路学报.2002,15(3):76-79
P208
B
1672-4623(2014)03-0054-02
10.11709/j.issn.1672-4623.2014.03.017
周瑞华,工程师,主要研究方向为计算机、GIS、GPS导航技术及应用。
2014-03-12。
项目来源:深圳市2013年度基础研究资助项目(JCYJ20130401145907839)。