配送路径优化

2024-12-10

配送路径优化（精选11篇）

配送路径优化篇1

摘要：文中通过应急物流的特点,研究了带时间窗的应急物流配送路径优化问题。建立数学模型,结合实例,采用lingo工具对所建立的模型进行求解,为解决应急问题提供了一种新的思路。

关键词：应急物流,时间窗,配送路径优化

1 引言

近年来我国发生了各类灾害疫情:2008年的冰灾、汶川大地震,2009年的旱灾、2010年青海玉树地震等,突发性灾害和公共事件的发生造成了巨大的人员伤亡和财产损失,其中应急物流带来的损失占其中20%左右。在突发事件发生后,救灾物资的配送是应急物流过程中一项极其重要的环节。本文针对突发性公共卫生事件的救灾物资配送问题,研究基于单时间窗的应急物资配送路径优化问题,建立了应急物资配送车辆路径优化模型,并利用LINGO对实例进行求解。

2 应急物流配送概述

应急物流是指为应对严重突发性自然灾害、突发性公共卫生事件、公共安全事件及军事冲突等突发事件而对物资、人员、资金的需求,借助现代信息技术,整合应急物资的运输、包装、装卸、搬运、仓储、流通加工,配送及相关信息处理等各种功能,以追求时间效益最大化和灾害损失最小化为目标的一种特殊物流活动[1]。

在突发性灾害事件发生之后,实现应急物流的过程中,其核心环节就是应急物资的配送。为了有效控制应急事件,使人力财力损失最小,我们首先应该解决的问题是配送路径的选择,实现在最短的时间内合理高效运用运输工具将受灾点所需的物资送达到受灾点。

3 应急物流配送路径优化问题的研究成果

赵彤等在《带时间窗的应急救助物资配送车辆路径优化路径模型》[2]一文中针对带时间窗的应急救助物资配送车辆路径优化问题进行研究,建立了以运输距离为目标函数的优化模型并运用了蚁群算法进行求解,取得了较好的效果。

仇戈在其论文《应急管理下的路线问题研究》[3]中结合实际情况建立了以时间为目标函数的应急物资车辆调度的模型,并且采用遗传算法,使用MATLAB予以实现,具有一定的借鉴意义。

白永秀、周溪召在《应急物资配送路径选择问题的研究》[4]中建立了以总时间、总成本、对物流服务的满意度的多目标规划函数的数学模型,并采用层次分析法来确定各目标的权重将多目标函数转化为单目标函数,具有一定的现实意义。

何小年、谢小良在《带装载量约束的物流配送车辆路径优化研究》[5]中建立了车辆数、行驶距离的多目标函数的车辆路径模型,设计了一种禁忌搜索算法,经过了多个算例测试比较显示出了明显的优势,对应急物流配送具有一定的指导意义。

本文根据应急物流的特点,建立了带时间窗、目标函数为配送时间的应急物流配送路径优化模型,依托于实例,用lingo进行求解,相比之下,具有快速简便的优势。

4 问题描述与模型建立

4.1 模型描述

某地区突发公共卫生事件,需要对各个受灾点运送药品,物资配送中心为该地某医药公司,位置已知,该配送中心拥有一定数量的车辆数,每辆车的载重量一定,有多个受灾点,每个受灾点需要多种药品,每个受灾点的位置以及药品需求量已知。在配送时间最短的条件下,如何合理配载车辆和安排配送路线,使每个受灾点能在规定的时间内得到物资,是本文要解决的问题。

基本假设:

(1)每辆车从配送中心出发,经过一系列的医院后返回配送中心,每辆车仅服务于一条路径。

(2)配送物资为多品种物资,配送车辆为单车型,载重量已知。

(3)每辆车可以为多个医院服务,但每个受灾点仅由一辆车服务。

(4)每辆车所服务的受灾点的需求总量不能超过每辆车的容量限制。

(5)每辆车服务其路径上的每个受灾点时,应在医院规定的时间前到达受灾点所在地。

图1应急物资配送车辆路径示意图

(其中□代表配送中心,△代表受灾点,→表示车辆行驶路径)

4.2 符号定义

K:配送中心的车队规模即总的车辆数目;

N:受灾点总数;

i,j:受灾点,i,j=(0,1,…,N),i,j=0代表配送中心;

dij:受灾点与受灾点及配送中心与受灾点之间的距离;

tij:从受灾点i到受灾点j的车辆行驶时间;

P:物资种类;

mpi:受灾点对物资a的需求量;

Q:车辆K的容量限制,假设所有车辆同质,容量均为Q;

ti:车辆到达受灾点i的时间;

li:受灾点要求物资到达的最晚时间;

RK:车辆K的访问路径(k=0,1,2…K);

S:路径条数;

V:车辆行驶速度;

模型建立如下:

式(1)表示求解目标即给定约束条件下最小配送时间(在这里忽略在受灾点的卸货时间)。式(2)、(3)表示对于救灾配送中心共有S条路径出发,同时又有S条路径返回到配送中心,且路径条数不能超过配送中心的车辆数。式(4)表示受灾点只能由一辆车服务。式(5)、(6)表示任意受灾点由第k辆车配送物资,该车从其他点驶入该点,并从该点驶出,驶入其他点。式(7)表示每辆车所承担的任务总和不超过该车辆的容量限制。式(8)表示到达受灾点j的时间等于车辆到达受灾点i的时间加上两受灾点间的行驶时间。式(9)表示车辆从受灾点i到j的时间等于两受灾点之间的距离除以车辆行驶速度。式(10)表示车辆需在受灾点规定到达的最晚时间之前到达。

5 实例分析

某地区突发公共卫生事件,需要对各个医院运送药品,物资配送中心为该地某医药公司,位置已知,有8个医院需要紧急救援物资,物资种类有两种,每个医院编号以及需求量已知,各个需求点允许到达最晚时间已知。车辆运输速度为1km/m,车辆数为5,车辆载重量为10t,配送中心以及各医院间的距离已知,配送中心对各医院送货,使每个医院在规定时间之内得到物资,同时使配送时间最短。

根据建立的模型,利用lingo编程求解,求解的状态如下:

可以看出,经过23分23秒的运算得到最优解min=132.

根据模型运行结果得到决策变量的值:

因此,得到四条条路径为:1-5-3-1;1-2-1;1-9-6-1;1-4-7-8-1。

因为在编程时将配送中心定义为编号1,医院定义为编号2-9,所以实际得出四条路径为:第一辆车的配送路径为:配送中心-4-2-配送中心;第二辆车的配送路径为:配送中心-1-配送中心;第四辆车的配送路径为:配送中心-8-5-配送中心;第五辆车的配送路径为:配送中心-3-6-7-配送中心。

车的装载物资数量如下:

6 结束语

对于物流配送路径优化问题,一般都根据问题描述建立数学模型,然后构造启发式算法对其进行求解。但是本文结合实例,对于建立的模型,直接用lingo编程求解。实例证明,用lingo来求解应急物流配送优化模型也是一种很好的方法,可以快速有效的求得应急物流配送路径的最优解。

参考文献

[1]刘玲.物流应急配送体系的科学构建[J].商场现代化,2010,(21),61-61.

[2]赵彤,范厚明,王桂琳,张靖瑶,董国松,李佳书.带时间窗的应急救助物资配送车辆路径优化路径模型[J].物流技术,2010,10,(227),63-68.

[3]仇戈.应急物流管理下的路线路径问题研究[D].成都:西南交通大学,2010.

[4]白永秀,周溪召.应急物资配送路径选择问题的研究[J].物流技术:2009,28,(3),88-91.

[5]何小年,谢小良.带装载量约束的物流配送车辆路径优化研究[J].计算机工程与应用,2009,45,(34),236-240.

配送路径优化篇2

摘要：物流配送是物流流程中的一个分支区域，一方面物流配送对满足顾客需求，完善输送系统、提高末端物流经济效益、降低企业库存、简化用户订货程序、提高企业保证供应的速度发挥着至关重要的作用。但当前风行牛奶配送物流存在各方面的问题，比如对物流配送认识存在误区、配送中心的配送比率低,配送成本高、配送中心设施落后、功能不全、物流配送模式选择不当、信息系统不完善,信息处理能力差、配送专业人才短缺,管理水平低下，针对这些问题，本文提出了相对应的对策，当前加快现代化配送中心的建立是配送发展的重点，加快信息化、自动化、机械化配送中心建设是未来的一个发展趋势。

关键词：风行牛奶

配送方案

优化

随着我国经济的快速发展和人类生活水平的提高，人们充分认识到健康的重要性，2008年三聚氰胺给乳制行业带来了信誉危机，奶粉的需求市场大不如前，成下降趋势。但人们对鲜奶的需求却呈增长趋势，谁的鲜奶在质量得到保证的同时，又能在最短时间内送到人们的手中，决定商家竞争市场的决定性因素。如今，鲜牛奶成为人们生活的必需品，送奶公司送奶的速度越快将赢得更大的发展空间。

广州风行牛奶有限公司是一家具有50多年历史的国有企业，是目前华南地区规模最大的专业乳品公司之一，并被国家统计局列为中国500家最大食品加工企业，公司拥有优质、充足的奶源，1992年被中国奶牛协会评为高产优质高效益奶牛场，1997年被中国绿色食品发展中心准予在生鲜乳上使用绿色食品标志，2004年2月份成立广州市奶牛生物技术中心，被评定为国家级良种奶牛场。公司在广东有500多个牛奶销售点，形成网络式服务，免费送奶上门服务。但是，由于鲜奶要求保鲜、风行牛奶配送中存在的问题迫切需要风行牛奶进行配送方案的优化，来提高牛奶配送比率，占据更大的市场份额。

一、配送的作用

配送就是主体单位根据生产企业所提出的要求和生产计划安排，在流通点对生产企业所需要的物资的类型、品种、标准、规格、所需物资的数量进行有关的加工处理、配备，并以最优惠的运输方式将企业所需物资按企业所规定的运送地点、需配送的数量按时送交生产企业。物流配送是伴随着大生产、大流通而出现的一种完成资源配置和满足消费需求的方式。物流配送由于其低费用、准时、定量甚至可以使得客户库存为零，使之完全可以代替客户原有的供应系统，同时供应给客户，实现了企业销售和客户供应的一体化。配送的作用主要体现在：

1、完善了输送及整个物流系统。配送对干线运输中心的社会物流功能体系起到了完善作用。通过配送作业，可以在一定范围内，可以实现干线、支线运输以及仓储的统一，从而完善、优化干线输送流程以及干线输送功能体系，形成一个大范围物流与局部范围配送相结合的、完善的物流配送体系。

2、提高了末端物流的经济效益。配送的发展对物流结构、产业结构可以起到优化和提升作用，实现运输业、仓输业的增长;同时带动与其相关的电信服务、代理业、客户服务的发展，从而为第三产业的发展作出新的贡献。

3、通过集中库存使企业实现低库存或零库存。配送通过配送中心集中库存的方式，将有限仓库更大程度上为更多的客户所使用，将大大地提高物资利用率、库存周转率。通过利用仓储与配送环节的规模经济优势，使得单位的存货和管理成本大大地降低。配送的目的在于尽可能地将流通时间缩短、使得流通成本降低，使得生产企业的库存量少或者甚至为零，从而使得社会的总成本得到降低。

4、简化订货程序，方便用户。配送可以根据用户要求准时、定量、按规格和要求送货上门，一方面减除了客户采购的车马劳顿之苦，将手续简化，成本降低，效率得到提高;另一方面使得物资供应得到了保证，保障企业的生产正常、有序进行，满足了人们的生产和生活需求，提高了生活质量。

5、提高企业保证供应的程度。企业零库存经营，将有大笔的流动资金可以用来改善企业的财务状况，提高企业的经济实力，从而促进企业的发展。企业的供应链将正常运转，可以随时满足客户的需求，将所需物资供应给客户。

二、风行牛奶配送中存在的问题

从目前风行牛奶配送的现状来看，配送还有一些不尽人意的地方急需改善和加强，主要存在以下几个问题：

1、对物流配送认识存在误区。公司对物流配送没有引起足够的重视，认识程度不高,将配送简单地理解为配货和送货,没有意识到以客户为中心的重要性。配送作为企业内部上通下联的节点,是企业提高生产效率、降低生产成本的途径,配送效率的高低对连锁经营超市的经营效益产生影响。

2、配送中心的配送比率低,配送成本高。风行牛奶连锁超市的配送比例都比较低,当然即时配送效率就更不理想,配送的出现差错和损坏的机会也比较高,这些问题对于牛奶生鲜食品来说存在致命的问题,使得“统一采购、统一配送、统一结算”的经营模式只是流于表面形式。

3、配送中心设施落后、功能不全。现代化配送中心的建立需要比较高的投入资本，且资本回收的周期比较长，为了节省成本，简单地将企业的仓库变成配送中心,没有自动化、机械化的装卸、搬运货物的设备，货物的搬运和装卸仍然由工力完成,这样将使得作业速度慢、作业效率低,货物损坏率比较高,没有完善的配送作业流程和体系。另外大部分的配送中心所属的仓库没有相对应的冷藏、保鲜功能,没有现代化的运输设备,从而使配送效率大减折扣。

4、物流配送模式选择不当。当前连锁经营超市的配送模式主要有四种:供应商自身配送、自建配送中心进行配送、共同配送、由第三方物流进行配送,企业应该根据实际的需要综合运用这些配送模式。各种配送模式有其各自的特点，连锁零售企业应该根据产品的特点和不同需求、规模选择适当的配送模式进行配送。

5、信息系统不完善,信息处理能力差。风行牛奶连锁经营超市没有建立完善的配送信息管理系统,大部分的信息都由人工进行操作和处理。即便部分企业建立了信息管理系统,但仍是冰山一角,处理信息的能力仍待进一步提高。企业内部局域网限制了电子数据交换,POS采集的信息未进行进一步的加工处理,信息反馈滞后,门店无法适应客户的需求和变化。

6、配送专业人才短缺,管理水平低下。当前缺乏精通连锁经营管理，熟悉配送运作模式、精通配送技术的复合人才,这阻碍了配送中心物流有效利用信息系统、充分利用现代物流产生。缺乏相关物流专业人才对配送中心的货位规划、加工处理物流信息和完善系统、科学拣选商的以及控制库存水平等产生影响,从而对整个物流配送中心的经营水平和管理水平产生深远影响。

三、风行牛奶配送优化

针对配送中存在的问题，现根据企业的发展和客户不断变化的需求，企业为了更好了提高服务水平，回快现代配送体系的建设，优化配送方案应该从以下几个方面着手：

1、树立现代物流服务理论，以顾客为上帝的宗旨。企业领导者应该充分认识到配送的重要性，不能将配送简单地理解为送货，而是以适应客户多样化需求、个性化需求为目的物流服务。应该追求服务水平的提高和服务内容的创新，为顾客提供差异化、量身定做的配送服务。

2、降低配送成本，提高配送比率。配送中心应该根据发展要求不断完善配送体系，进行精益化的配送管理。精益化的核心在于以最少的成本投入获得最大的收益，用很少的人力、物力、财力、时间、创造出更多的经济价值。在规模扩大的同时注重结合运用科技手段，提高配送效率。

3、建立功能齐全的配送中心、采用先进的物流设备。

高效的物流配送需要采用先进的技术、先进的设备更好地销售服务，生产的规模越大、销售规模越大、范围越广，物流配送技术、设备及管理越现代化。配送中心应该具有冷藏、保鲜功能，要具有基本的分拣设备。装卸、搬运都应用用机械化、自动化的作业设备，比如吊车、叉车、传送带。

4、根据自身的实际要求选用合适的配送模式

当前物流配送具有供应商自身配送、自建配送中心进行配送、共同配送、由第三方物流进行配送等四种配送模式，企业和连锁超市应该根据自身规模的大小、经济实力、客户的要求选择适合自身的一种物流配送模式，既可以提高配送效率，又可以降低配送成本，同时也满足了客户的订货和配送要求。

5、建立完善的信息配送系统，使得配送组织网络化。为了使得产品促销实现快速化、全方位的配送，要有健全、完善的物流配送体系，网络上点间的配送要保持一致，从而使得整个配送网络库存及分布送到最优化，配送及运输快捷化、机动化。用运用先进的配送信息系统，提高信息管理技术水平，做好信息系统的维护和开发。

6、加强配送专业人才的培养。现代物流离不开系统化、高效的管理体系，同时也与现代的管理技术术、管理思想密不可少。而这些最终离不开人的支持，对配送人才的培养是当现代物流面对的重要问题。加强配送专业人才的培养，配送中心应建立相应的物流培养机构，对员工进行定期的物流培训或岗位轮流训练。对物流配送中心的管理人员进行系统的计算机应用技术和现代物流知识培训。另外，也可以通过与学校合作进行订单式培养，从学校选用专业的物流人才。

四、风行牛奶配送发展趋势

随着电子商务的进一步发展和繁荣，随着物流技术水平的提高，为了顺应时代潮流，未来物流配送行业将呈现良好的发展势头，风行牛奶将建立现代化的物流配送，将呈现以下发展趋势：

现代化的物流发展需要现代化技术、装备作为支持后盾。订货与配送密切联系为一体，配送依赖于先进的信息技术水平。配送规模、配送水平、配送效率、与传统的送货方式相比，规模更大，配送水平和配送效率更高，而需要借助于传输设备及识码、分拣设备。电子商务时代发展下所要求的物流配送，将集信息化、现代化以及社会化于一身。

参考资料

1、吴静旦.我国零售连锁企业物流配送策略探析[J].中国科技信息,2007(15).2、张卫星,王欣.家电连锁零售业物流配送现状及优化研究[J].中国市场,2008(45).3、秦瑛,陈竹君,陈丹晔.我国中小型连锁企业的物流配送模式的比较选择[J].中国市场,2008(28).4、张丽华.物流配送中心的问题分析及对策[J].经济管理,2009(12).5、曹宝亚.基于物流信息化下的配送研究[J].中国集体经济,2008(1).6、张朝霞.连锁超市物流配送方式的优化[J].山西经济管理干部学院学报,2008(4).7、徐贤浩.物流配送中心规划与运

平安汽配快运的配送优化篇3

关键词：鑫盛平安汽配快运；配送管理

一、配送的含义

中华人民共和国国家标准《物流术语》将配送（Distribution）定义为：在经济合理地域范围内，按照用户需求，对货物的选择、加工、包装、分割、组配等作业，并按时送达指定地点的物流活动。从定义中可以看出，配送几乎包含了物流的全部功能要素（拣选、加工、包装、分割、组配），是在一个经济合理地域范围内所有物流活动的体现。通过拣选、加工、包装、分割、组配等活动，完成将物品送达客户的目的。

二、平安汽配快运配送的不足分析

（一）缺乏统一的配送计划

平安快运的配送现状显示，其每日的配送是根据以往的经验来进行车辆人员与支出的安排，并没有科学可行的配送计划。没有计划的盲目配送不但导致资源浪费，增加配送成本，也会影响客户满意度。

（二）未将汽车配件分类，影响配送效率

汽车物流是物流系统中最广泛、技术最复杂领域里最重要的一部分，物流配送是物流系统运行和持续优化的关键环节。在配送的每个环节中都应该注重其货物即汽车配件的各种特性，不论是配装还是运送，汽车配件的特殊性都应要求将货物分类。这样可以减少货物损坏率，减少客户纠纷，提高配送效率。然而，平安快运在集货和配装的过程中并没有将汽车配件分类，只是单纯的将货物按目的地分类，忽略了汽车配件的特殊性，导致在装货和卸货过程中的造成不必要的损耗。

（三）配送流程过于粗放，影响服务水平

保障配送顺利进行的前提条件是有一个规范的配送流程，汽配货物的配送过程和大多数的物流配送过程相差无几，即集货，分拣，配货，配装，配送运输，送达服务和配送加工。平安快运在货物分拣方面缺少专业的设备与技术，在货物分拣时缺少专业知识的支撑，导致分拣货物效率低，分错货物时而发生。并且，忽略了配送的配装环节，尤其是车辆配装，没有很好的考虑车辆的载重量和车辆的容积，导致车辆分配不合理，造成人力和车量资源的浪费。

三、平安汽配快运的配送提升途径

（一）制定配送计划

合理的配送计划是提升配送管理效果的首要环节，根据实际情况，平安汽配快运应该在在制定配送计划时首先确定配送计划的目的，然后收集相关数据资料，结合配送环节中的所有要素，以自己的配送目的为先导，利用收集到的资料制定初步的配送计划，接着将初步的配送计划告知客户，根据客户要求，结合自己的实际情况对初始的配送计划进行最终的完善、调整，最后确定客户认可、切实可行的配送计划。

（二）将汽车配件分类，提高配送效率

平安快运是专营汽车配件配送的企业，由于汽车零配件种类繁多，以及价值差异很大，所以在配送过程中应将货物分类配货与运输，以提高配送效率，减少货物损失。

按照使用价值和使用频率可将汽车配件分为A、B、C三类。A类零配件价格最贵，通常为非通用件，种类不多，例如发动机总成、车门、排气管、减速器等。B类零配件价格较高，种类较多容易混淆，主要有显示器、蓄电池、汽车地毯、车载对讲机等。C类零配件价格低，主要为标准件，汽车生产厂家的备件消耗量大，较稳定且运输频率低。每次运输都将使用相同的包装容器，同样的运输，如雨刮器、方向盘、牌照架、安全带等。不同种类的汽车配件应有不同的包装与装卸模式，并且分类后的汽车配件更有利于配装与车辆调度的优化。

（三）规范配送流程，提高服务水平

平安快运在配送流程上过于随意，忽略了分拣、配装和配送加工的流程问题。在货物分拣中，分拣人员缺少对分拣专业知识和汽车配件的了解，货物混装和货物损坏的情况时有发生，针对于这种情况，可利用将汽车配件分类的办法进行解决。而对于车辆配装的问题，平安快运对此是没有按照科学的方法进行车辆配装，甚至忽略了车辆配装的问题，每次装货都以将货物塞上车便完事。

事实上在装车时，不仅要考虑车辆自身的载重量，还要考虑车辆的容积，让车辆的载重和容积都能获得合理地使用，配送车辆配装技术要解决，主要问题便是在充分保障货物质量和数量完整的前提条件下，尽量增加车辆的装载率，增加车辆的利用率，节约运力，降低配送成本。

最后，平安快运基本上忽略了配送加工这个步骤，尽管配送加工这一功能要素不是普遍存在的，可是经常起着不可忽视的作用。因为通过合理的配送加工，能够大大提高用户的满意度。配送加工属于流通加工的一种，但配送加工又不同于一般流通加工，即配送加工一般只满足用户要求，其加工的目的较为简单。平安快运可增加配送加工这一环节，并按客户要求对汽车配件进行加工，从而让配送环节增值。

参考文献：

烟草配送系统中路径优化问题篇4

目前我国绝大多数烟草企业仅以人工、凭主观、靠经验对配送线路进行优化,也有少部分企业开始借助于信息技术实现配送线路的优化工作,但能够提出完整的物流配送线路优化系统的企业还非常少。而国外的一些路径优化软件由于交通规则、道路规划等各方面不符合我国国情,很难符合改革中的中国烟草的管理流程,因此烟草配送路径优化问题已成为制约我国烟草物流发展的主要因素之一。

目前,国内外大多数研究很难一次性形成合适的配送线路,往往需要辅助很多人工干预和调整,增加了工作的复杂性。本文将中国邮路问题引入配送路径的优化中,在邮路问题中引用指派问题来处理奇点对之间增加重复边的问题,大大简化了多奇点对之间增加重复边的繁琐性,试图寻求一种新的适合我国烟草配送系统的路径优化方法,并力求有所突破。

2 烟草配送路径优化模型

2.1 模型建立的前提条件及符号规定

本文结合我国烟草配送的特点,建立了市区间的烟草配送路径优化的模型,其前提条件如下:

(1)某市卷烟零售网点分布在全市各地,其总体数量大致稳定;

(2)该市根据配送辐射半径,将全市划分多个配送区域,并确定每一区域的配送中心及每个配送中心所覆盖的零售网点;

(3)零售网点的配送任务由所在区域的烟草配送中心负责,所有配送车辆为同一型号,每一区域的烟草需求量都必须在单车车载量以内,区域内各零售网点所在道路的长度可知;

(4)配送车辆由某一区域的配送中心出发,经过该区域内各零售网点,配送完成后车辆返回该物流中心。

符号规定如下:N为某烟草配送区域内零售网点d的个数(d=1,2,…N);Xd表示配送路径是否经过第d个零售网点(Xd=1时表示经过,Xd=0是表示未经过);G=(V,E)为该区域零售网点所在道路形成的边权连通无向图;V为道路交叉点的集合{v0,v1,…vn},点数|V|=n,其中v0表示该区域的烟草配送中心;E表示G中所有道路的集合{(vi,vj)},道路个数|E|=m,(i,j=0,1,…,n);W(vi,vj)表示道路(vi,vj)的长度;r表示G中奇点个数(必为偶数);vkp、vkq表示G中的某两个奇点,(p,q=1,2,…,r);fpq表示vkp与vkq之间的最短距离(p≠q);C为从烟草配送中心出发经过每个零售网点后重新回到配送中心的一个配送路径;L(c)表示配送路径C的总长度。

2.2 模型描述

对于某一个烟草配送区域,零售网点是固定分布在道路上的,可将配送路径必须经过零售网点的问题转化为必须经过零售网点所在道路的问题,这样如果配送车辆能以最短路线遍行零售网点所在的道路,即能完成送货任务。所以在道路(vi,vj)的长度W(vi,vj)可知的边权连通无向图G=(V,E)中

目标函数为:min L(c)

该问题在本质上与中国邮递员问题是一致的,故我们把该烟草配送最短路径问题,转化为求解网络图的中国邮递员问题。

3 案例应用

某市一烟草企业的物流配送具有客户多、批量小、品种多、时间要求高的特点,该企业按照单车车载量将本市划分为多个区域,每一区域分别由该地区的配送中心来进行分配,如图1是该烟草企业的某个配送区域,在该区域有18个零售户(图中用方格“□”来表示),分别固定分布于不同的街道,区内每条道路的长度如图中所示,A为该配送区域的物流配送中心,V1至V12为街道的交叉口,该配送区域构成如下的边权连通无向图,目前该烟草企业在该地区的配送路线为:A—V1—V2—V3—V10—V1—V10—V3—V4—V5—V6—V7—V8—V11—V12—V4—V12—V6—V7—V8—V11—V10—V9—V8—V9—A,配送路径的长度L(c)为140。

采用中国邮递员问题算法,利用C语言编程,在WINDOWS XP环境下运行得到各个奇点的两两配对的最优匹配方案:即v1,v11配对,v3,v4配对,v6,v12配对,v8,v9配对。对两两配对的奇点添加重复边得欧拉图G*,如图2所示。

在图2中,所添加重复边的路径之和为f17+f23+f48+f56=14,此时配送路径C的长度L(c)=96+14=110(<140)即为该配送区域内的最短路径,从配送中心A出发找出欧拉回路:A—V1—V2—V3—V10—V1—V10—V11—V12—V4—V3—V4—V5—V6—V12—V6—V—V8—V9—V10—V11—V8—V9—A,此回路即该配送区域内送货车辆的最短行驶路线。显然,求出的最短配送路径远远小于目前该烟草公司的配送路径长度。考虑到现实配送过程所耗费的人员和车辆等费用后,该烟草公司改用最短配送路径后可大大提高配送的效率,并将节省大量物流成本。

4 结论

本文利用中国邮路问题的最短路径算法,并对优化后的最短路径算法进行了语言编程,能快速求出每个烟草配送区域内的最短路径和最优路线,使得烟草配送最短路径的实时计算成为现实,其成果在烟草的区域配送系统中具有普遍适用性和广阔的应用前景。

参考文献

[1]戢一鸣.基于GIS的现代物流系统配送算法的研究与应用[J].武汉理工大学学报,2004,26(5):154-156.

[2]Alvarenga,G.B.&Mateus G.R..A Genetic and Set Partitioning Two-phase Approach for the Vehicle Routing Problem with time windows[J].Computers&Operations Research,2007,34:1561-1584.

[3]Dondo,R.G.&Cerda,J.A hybrid local improvement algorithm forlarge-scalemulti-depotvehicleroutingproblemswithtimewindows[J].ComputersandChemicalEngineering,2008.10:1003-1016.

[4]Asvin Goel&Volker Gruhn..A General Vehicle Routing Problem[J].European Journal of Operational Research,2008,191:650-660.

配送路径优化篇5

物流配送中心优化布局的运筹模型分析

利用DEA模型对配送中心布局方案进行评价,结合评价结果建立复合整数规划模型来对原方案进行重新调整,最后给出了算例.

作者：徐兵吉阿兵 XU Bing JI A-bing 作者单位：徐兵,XU Bing(南昌大学,管理科学与工程系,江西,南昌,330047;复旦大学,管理学院,上海,33)

吉阿兵,JI A-bing(复旦大学,管理学院,上海,200433)

刊名：南昌大学学报（理科版） ISTIC PKU英文刊名：JOURNAL OF NANCHANG UNIVERSITY(NATURAL SCIENCE) 年，卷(期)： 29(6) 分类号：N945.16 关键词：选址模型 DEA 整数规划

基于动态规划的物流配送优化研究篇6

[关键词] 物流配送动态规划优化

一、问题的提出

物流配送是物流管理活动的一项核心技术。要高效地完成配送任务就得对配送路线进行合理安排。目前，出现了较多关于物流配送的研究，如物流网络及其优化、物流配送的动态规划算法等。

但上述的研究仅将配送路径最短作为目标函数，有其局限性且过于简化。在实际的运作中，货物经过每层配送时中，并非只是简单地流经、通过，而是要进行存储、装卸、转运等必要的运作，这就产生了不可忽视的费用（统称为存转费）。故物流配送是一个多层次运作，不光考虑运输费用，还要关注存贮费用，且两者必须统筹兼顾。

二、物流配送优化模型

物流配送的运营方式从本质上讲是运输、存转、运输、存转……循环交替的复杂的多阶段过程。故可以利用动态规划的思维来考虑问题。

该动态规划可分为N个阶段，第i(1≤i≤N)个阶段可供选择的状态(分销商)有Si个，任意阶段i的状态和目标状态之间的费用关系可以用费用矩阵M(r)（共有Si×Si+1个）来表示，每个元素表示阶段i的状态mi和阶段i的目标状态mi+1之间的费用消耗。特别地，规定表示第i阶段目标状态的存转费。如果mi到mi+1没有配送路线的设计，则可认为其间的费用为a∞(mi,mi+1)。则物流配送优化模型为一个二元函数:min F=K+C （K为总运输费，C为总存转费）。

三、模型求解

依据动态规划思维及贝尔曼最优化原理，则模型的求解可化为特殊的矩阵运算。其求解思想是：将存转费转化到运输费当中去，再利用矩阵运算进行问题的求解。

定义1阶段i的状态到阶段i+1的目标状态之间的费用在经过阶段i+1时的状态t(同时也是阶段i的目标状态)时第i阶段目标状态的存转费的转化为:

存转费的前向化:

存转费的后向化:

定义2阶段i的状态到阶段i+1的目标状态之间的费用在经过阶段i+1时的状态t(同时也是阶段i的目标状态)时为:

定义3阶段i到阶段i+1的的费用矩阵可以通过如下的计算求得:

M(i)M(i+1)=

定理多个连续阶段i,i+1,L,j的费用矩阵的复合关系记为。

四、实例分析

上图是一个简单的有向网络图。具体的计算过程如下:

1.存转费的转化。（本文采用存转费前向化方法）

则有：

2.费用矩阵为:

3.利用逆序解法，有

同理有：

可见,图中的最小费用为51,而且最优的配送路线为A,B1,C3,D2,E。

五、结束语

本文提出的基于矩阵运算的最小费用配送路线求解方法，为决策者提供了一种新的优化方案。另外，还可以进一步研究多品种、分批量的配送优化等问题。

参考文献:

[1]石永泽:物流技术应用讲座[J].物流技术,1996,(5)

[2]刘虹孙金梅陳德运:一种基于供应链管理的动态规划算法[J].哈尔滨理工大学学报,2003.(4)

冷链物流多温配送路径优化研究篇7

目前我国冷链物流配送的发展很快,粗放式的发展造成成本急剧增加,配送环节成本就占总冷链运营成本的35% ~60% ,但是在对冷链配送的研究中,突出的问题是大多数研究是对冷链物流配送车辆路径的优化,而忽略了冷链配送中货物对温度的要求和成本的考虑,这使得在实际配送过程中造成配送的成本高昂和货损严重。只利用常温配送路径优化的模型不能很好地控制冷链物流总成本,基于此本文在利用常温配送车辆路径方法基础上,考虑到多温共配的成本特殊性,同时加入软时间窗的限制,尽可能解决配送路径优化与成本之间的矛盾。

2 基于配送总成本的多温共配模型构建

在建模过程中,需要使配送过程的总成本达到最优,所以本文将总成本分为车辆的固定成本、货物的配送中制冷成本、货物在运输途中的货损成本、装卸搬运时的货损成本和因违反时间窗约束而产生的惩罚成本。综合各部分成本建立多温共配的总成本模型。

2. 1 参数设计

m为运输车辆的数量; n为客户总数量; v为每单位路程运输成本; f为每辆车的固定成本; dij为客户i到j的距离a1为运输过程中的货损系数; a2为搬运过程中的货损系数Yi为客户的货物需求数量; xi为送货到达的时间; 为货物价格; β 为未及时送达的惩罚成本; P1为制冷剂价格; R为载货量; S为车体内部的表面积; T1，2，3，…，n为不同货物所需的不同温度; ti为在客户i停留时间; Tij为车辆从客户i到客户j所用的时间; G为制冷剂的消耗量。

2. 2 多温配送各部分成本的确定

2. 2. 1 车辆的固定成本

固定成本主要包括车辆以及车载设备的购买、折旧; 驾驶员与工人的工资等。固定成本的表达式为:

2. 2. 2 配送车辆的运输成本

配送车辆的运输成本包括车辆的油耗、维修、保养和过路费等。在运输成本中由于本文加入软时间窗的限制,所以考虑到在一线城市中市内堵车的情况,运输配送的路线选择,以及时间的要求,都会影响到运输成本。其表达式为:

2.2.3配送运输过程中的货损成本

在低温环境中,货物的保质期会延长,超出保质期的货物就会变质,这部分的损失就是运输过程中的货损成本。其表达式为:

2.2.4装卸搬运时的货损成本

运输车辆在配送中心装车和到达客户时卸货的整个过程中货物会发生损坏,并且在装卸时开关车门会影响车内温度的变化,加快货物的损坏速度。这部分成本称之为装卸搬运货损成本,其表达式为:

2. 2. 5 惩罚成本

本文采用软时间窗的做法,如果货物不能在规定的时间范围内送到客户手中,则给予一定的惩罚。以a3和a4分别表示车辆提早和迟到带来的单位损失成本,如果货物提前送到,则会产生a3( Ej- sj) ,如果配送迟延,则产生a4( si-Tj) ,由此可以得到惩罚成本函数:

2.2.6制冷成本

冷藏设备工作时需消耗制冷剂,对每辆车来说,由于车体内部的表面积、车厢材质传热系数和外界的温度等影响因素不同,制冷成本也各不相同。使用制冷剂则消耗的制冷剂的量为。则制冷成本函数为:

根据以上各部分的成本可以得到配送过程中总的成本:

3 常温配送与多温共配的总成本比较

根据某配送公司的一个配送点的实际成本来检测以上配送路线是否最经济,表1 为系数表。

由Matlab运行出来的结果看,常温配送车辆行驶路线1 号车0—7—6—1—0; 2 号车0—3—5—0; 3 号车0—4—8—2—0。多温共配最优配送路线: 0—3—5—7; 0—1—4—6; 0—8—2。

计算过程中所需要的车辆配送时刻表如表2、表3 所示。

由上文给出的总成本函数可以得到常温模式和多温共配的配送总成本比较,如下表4:

该实例最终证明,在软时间窗的前提下,实行多温配送的方式,不仅能提高配送效率,降低货损成本,而且还能给冷链物流的研究提供一定的理论指导。

5 结论

在冷链配送过程中,大部分货物都是易腐烂的,多温配送考虑到了货物配送过程中的温度要求,同时也把路径优化和时间窗加入限制条件中。从上表可以看出,多温共配的总成本比常温模式配送要小,总优化率为9. 55% ,这在大规模配送运输中节约的成本总数是相当可观的; 再从各部分成本比较,惩罚成本和制冷成本有所上升,这方面随着技术的革新,成本也会随之下降。采用多温共配方式,其运输成本和多温层货物的常温配送方式相比,能更好地对配送路径进行优化和对时效性的把控。

摘要：传统的冷链物流配送过程中既容易造成货损和环境污染,又不利于货物配送半径的扩展和客户对货物的质量要求。本文在考虑货物配送过程中对温度的要求之外还加入传统的路径优化和时间窗的限制,在配送总成本最优的情况下进行冷链物流配送。

关键词：多温共配,成本模型,软时间窗,路径优化

参考文献

[1]唐珍.冷链物流多温共配的优化研究[D].烟台:烟台大学,2013.

[2]牛燕青.基于随机情况下的多温共配冷链物流配送方案研究[D].烟台:烟台大学,2014.

基于物流配送路径的优化算法研究篇8

1 物流配送路径优化问题的精确算法

1)动态规划法。此算法(dynamic programming)是运筹学的一个分支,是求解决策过程(decision process)最优化的数学方法。动态规划算法通常用于求解具有某种最优性质的问题。在这类问题中,可能会有许多可行解。每一个解都对应于一个值,我们希望找到具有最优值的解。动态规划算法与分治法类似,其基本思想也是将待求解问题分解成若干个子问题,先求解子问题,然后从这些子问题的解得到原问题的解。

2)分枝定界法。该法是将原始问题分解,产生一组子问题。分支是将一组解分为几组子解,定界是建立这些子组解的目标函数的边界。如果某一子组的解在这些边界之外,就将这一子组舍弃(剪枝)。分支定界法原为运筹学中求解整数规划(或混合整数规划)问题的一种方法。用该法寻求整数最优解的效率很高。将该法原理用于过程系统综合可大大减少需要计算的方案数日。

3)切平面法。此方法与分枝定界法相类似,它也是在整数规划与求解相对应的线性规划上,不断的增加新的约束,相区别是会加入一些特别的约束条件,然后切掉非整数规划中的可行解,获得最优解。

2 物流配送路径优化问题的传统启发式算法

传统的启发式算法在求解过程中主要是从初始解出发,以搜索邻域的方式实现解的改进,并在较短的时间内获得一个可以接受的解。传统的启发式算法主要有以下4种:1)节约算法。此算法是将较短路径与原路径定义为节约值,然后将节约值从大到小进行排序,在节点的数量允许的情况下,依此将节点对应的顾客点插入到路径中,直到所有的顾客都被插入路径为止,从而获得可行解,不过解非最优。2)邻接算法。此算法是由数据结构中的邻接表演变过来。邻接表是图的一种链式存储结构,对图的每个顶点建立一个单链表(n个顶点建立n个单链表),第i个单链表中的结点包含顶点Vi的所有邻接顶点。此算法的思想是从一个起始点出发,然后搜索路线中与之距离最近的点,然后在次以此方法不断搜索最近的点,从而进行路线的构造。这种方法可以保持原有路线的可行性,从而搜索着一条疑似最短的路线,节约路线成本。3)插入算法。此算法是又数据结构中的插入排序演变过来。它将邻接算法与节约算法有机的结合起来,先利用节约算法确定一条基本路线,然后根据邻接算法搜索客户节点的位置,依次按距离将客户节点插入到原有路径中,最后形成新的配送路线。4)扫除算法。此算法是将邻接算法与插入算法相结合,它是先对车辆进行分组,然后确定不同的路线,在配送过程中以扫除的方式搜索未被分配的点,然后用插入算发对路线进行扩充,如果一次分组之后还存在未被分配的点,那么继续对路线进行构造,直到所有的点都被分配为止。

3 物流配送路径优化问题的现代启发式算法

与传统的启发式算法相比,现代启发式算法并不是每次在迭代中都延着目标值下降的方向进行搜索,它还允许在搜索中接受目标值上升甚至是不可行的解,现在启发式算法与传统启发式算法的一大区别就是它会在搜索过程中跳出局部邻域进行全局搜索。现代启发式算法有以下4种:1)禁忌搜索算法。此算法是一种亚启发式(meta-heuristic)随机搜索算法,它从一个初始可行解出发,选择一系列的特定搜索方向(移动)作为试探,选择实现让特定的目标函数值变化最多的移动。为了避免陷入局部最优解,TS搜索中采用了一种灵活的“记忆”技术,对已经进行的优化过程进行记录和选择,指导下一步的搜索方向。禁忌搜索是对人类思维过程本身的一种模拟,它通过对一些局部最优解的禁忌(也可以说是记忆)达到接纳一部分较差解,从而跳出局部搜索的目的。2)遗传算法。此算法是模拟达尔文生物进化论的自然选择和遗传学机理的生物进化过程的计算模型,是一种通过模拟自然进化过程搜索最优解的方法,它最初由美国Michigan大学J.Holland教授于1975年首先提出来的。遗传算法从问题解的串集开始嫂索,而不是从单个解开始。这是遗传算法与传统优化算法的极大区别。传统优化算法是从单个初始值迭代求最优解的,容易误入局部最优解。遗传算法从串集开始搜索,覆盖面大,利于全局择优。遗传算法是基于生物进化的原理发展起来的一种广为应用的、高效的随机搜索与优化的方法。其主要特点是群体搜索策略和群体中个体之间的信息交换,搜索不依赖于梯度信息。3)模拟退火算法。模拟退火算法来源于固体退火原理,将固体加温至充分高,再让其徐徐冷却,加温时,固体内部粒子随温升变为无序状,内能增大,而徐徐冷却时粒子渐趋有序,在每个温度都达到平衡态,最后在常温时达到基态,内能减为最小。此算法是一种随机松弛技巧,它模拟了退火的过程,在搜索的初始阶段,算法跳向远点,随着时间的延伸或下降,跳跃幅度逐渐减小,最终转向局部搜索的下降方法。4)蚁群算法。蚁群算法又称蚂蚁算法,是一种用来在图中寻找优化路径的机率型算法,其灵感来源于蚂蚁在寻找食物过程中发现路径的行为。在每只蚂蚁能感知的范围内寻找是否有食物,如果有就直接过去。否则看是否有信息素,并且比较在能感知的范围内哪一点的信息素最多,这样,它就朝信息素多的地方走,并且每只蚂蚁都会以小概率犯错误,从而并不是往信息素最多的点移动。蚂蚁找窝的规则和上面一样,只不过它对窝的信息素做出反应,而对食物信息素没反应。

4 各种优化算法的比较

以上各种优化算法在不同时期与情况下都有其优缺点,都有解决某些问题的能力,但随着发展的需要,对优化算法的要求也越来越高。下面对各种方法进行比较分析,通过表格的形式展示出各自的特点,如表1所示。

5 结束语

车辆路径问题由于在管理学和运筹学上非常重要而且求解有一定的难度,同时由于它具有很强的现实价值,可产生极其可观的经济效益,因而是理论界与企业界关注的一个极其具有魅力的优化问题。通过表格的分析比较,可以看出各种方法的优点和缺点,在不同的任务中可以挑选不同的优化算法,从而使物流效率达到最高。本文通过介绍各种优化算法来比较各类算法的优缺点,以便能在实际中解决各种复杂的物流路径优化问题,从而找到最好的优化方法。

参考文献

[1]孙学农,徐辉增.物流配送车辆调度问题方法综述[J].科技信息:学术研究,2007(12).

[2]刘明广,李高扬.物流配送车辆优化调度模型及其求解策略[J].工业工程,2007(2).

[3]方金城,张岐山.物流配送车辆路径问题(VRP)算法综述[J].沈阳工程学院学报:自然科学版,2006(4).

[4]李贵春,刘冬梅.物流配送系统车辆的优化调度算法[J].天津工业大学学报,2006(3).

物流配送车辆路径优化的仿真分析篇9

1配送车辆路径优化问题的提出

具体而言,此问题的目的在于完成货物配送任务的过程中,以最少车辆数、最小车辆总行程去完成,这样就可实现时间最短或成本最小的目标,在路径的优化方面,有启发式算法、精确算法等多种类型,但都不够完善,存在各自的缺陷,难以获得最短路径的最优解,而最近几年出现的遗传算法等存在收敛速度慢、求解时间长的缺陷,这使得其往往只能找到近似最优解,存在一定的局限性,而本文研究的蚁群算法表现为一种群智能优化,在巢穴和食物间的最短路径的寻找方面,其借助正反馈并行机制和蚂蚁间协作来实现,优势较多,如求解速度快、具有并行性等,有着广泛的应用前景[1]。

2建立数学模型

具体实施中,走什么样的路线进行运输显然是物流配送车辆调度的实质,在已知客户需求量及车辆载重量的前提下, 为实现需求且车辆的总行程最短的目标至少需要派多少辆车,这就是最小成本的配送方案的由来,需对以下条件进行满足: 首先是以配送中心为起点,对应的配送车辆能最终回到配送中心; 其次,每辆车只能服务一条路线,同时每个客户只被一辆车访问一次; 再次,以车辆的载重量为基础,每条配送路径上客户需求量之和不能超过它; 最后,则是不能重复走每辆车的路线。基于上述要求,显然找到一条最优物流配送路线即为物流配送车辆路径优化的目标,从而实现最小配送费用。 V = { v0,v1,…vn} ,v0为配送中心,客户的所在地用vi表示,设K为配送中心可最多用的车辆数目,对应的Qi则为每辆车载重量,这样,我们就可借助建立的数学模型表现物流配送车辆路径最优化算法问题[2]:

上式中,k辆车所配送的顾客点数用nk表示,而顾客点在路径k中的顺序为i则用rik表示,最优解的限制条件如下:

2蚁群算法主要内容

近年仿生优化算法的发展速度较快,得到了很大的应用, 蚁群算法主要通过模仿来取得问题的解决,该算法的基本思想主要是对蚁群的觅食过程进行必要的模拟,所求问题主要是可行解集,在最优解的求解,是借助蚁群的正反馈和分布式协作机制来进行的,利于对二次分配及作业安排调度等方面的求解。

3配送车辆路径优化的蚁群算法设计

首先进行的步骤为确定蚁群数目,对应的我们设有n个客户数,m为蚁群中的蚂蚁数,则有:

式中,t时间位于客户i的蚂蚁的数目即为bi( t) 。

另外,主要规则是对蚂蚁路径转移规则的研究,本文所探讨的物流配送车辆路径问题中,其转移概率势必要对下一个客户点路径长度和路径上的信息素浓度进行考虑,物流配送中心可用O表示,j表示能够访问的客户点。这样,k到i向j选择转移的公式如下:

若j∈Q,否则( 4) 式中,tij表示i到j所有d时间,tij表示权重系数,β 表示期望启发式因子,α 表示信息启发式因子,ηij( t) 表示与路径( i,j) 相关联的启发式信息值:

再次,为信息素更新规则。为了充分利用循环最优解,需要对不同蚂蚁信息素进行循环,循环之后进行更新,如下公式:

其中,信息素挥发系数为 ρ,表示为[0,1]间的随机数,信息素残留因子用1 - ρ 表示,而本次循环过程中路径( i,j) 上的信息素增量则用 Δτij( t) 表示,对应的,本次循环中残留在路径( i,j) ,第k只蚂蚁的信息素总量用 Δτkij( t) 表示,继而出现:

其中,Q在式中作为常数,既信息素浓度,第k只蚂蚁在一次循环中的路径用Lk表示。

4车辆配送路径算法的实现

当前物流业发展中,对车辆配送路径优化问题的求解方面,借助于蚁群算法的方式,可借助人工蚂蚁替代车辆来服务客户点来实现,返回到配送中心的标准是下一个服务客户点会使运载总量比最大距离超过一次最远行驶距离或是汽车载重量更多的时候,不同车辆完成的此次运输,在此基础上,车辆可以对其他客户进行全方位服务,继而该车辆的人工蚂蚁就可以完成一次巡游标志,该标记是对客户进行的一次服务, 一次服务也可以是一次循环,之后,需要根据蚂蚁巡游路径的好坏程度将其他信息素进行分配,从而更好的对信息素增量进行不同程度的更新,以此进行不断的更新,得到最优路径或是选择相同路径,这样就可以完成求解了。

5结束语

综上所述,本文为达到对物流运输系统中车辆的路径的合理规划,本着对物流企业经济效益提高的目的,积极分析了物流配送车辆路径优化问题,后续研究中利用蚁群算法鲁棒性强等特点,在对此问题进行求解的方面提出一种基于蚁群算法,后续检验证实,本方法提高了寻优效率,对于最优解能快速找出,此方法具备了广阔的应用前景。

摘要：当前物流行业发展中,基于行业的发展需要,以及传统物流在降低物流运输成本方面无法克服的短板,急需进行物流配送车辆路径优化,从而有效地降低物流配送成本,基于此,文中提出一种蚁群算法的物流配送车辆路径优化算法,旨在建立数学模型的基础上,对物流车辆路径的问题采用蚁群算法进行求解优化,后续实验得出,该算法效果显著,利于对物流配送成本的降低,对于当前物流企业的发展意义重大。

物流配送中的车辆路径优化问题篇10

关键词：配送,车辆路径问题,时间窗,遗传算法

随着经济全球化趋势的加强,科学技术尤其是信息技术的发展突飞猛进,产品营销范围日趋扩大,社会生产、物资流通、商品交易及其管理方式正在发生着深刻的变革,与此相适应,被普遍认为企业在降低物资消耗、提高劳动生产率以外的“第三利润源”的现代物流在世界范围内广泛兴起,目前正在成为全球经济发展的一个重要热点和新的经济增长点。随着传统批发、交通运输、仓储业向现代物流转化,尤其是配送方式的采用,对运输成本和时间的有效控制日渐成为城市配送车辆路径问题的一项重要目标。V R P一直以来都是车辆调度所重点研究的方向。而在城市内采取的配送方式恰恰具备了V R P问题的一般特征和优化调度条件。

一、VRP模型的条件及假设

V R P问题是指按要求用多个车辆从配送中心对顾客进行配给货物。各顾客点的位置和需求量为己知,各车辆的装载质量己知,力求寻找一个好的配送方案,使得总代价最小(车辆尽量少,行车总距离尽量短,总费用尽量低等),由VRP的定义不难看出,必须满足以下条件及假设:

1. 仅考虑位置已知的单一配送中心,所有的配送车辆以配送中心为起点,并最终回到配送中心。

2. 每条配送路径上各需求点的需求量之和不超过车辆的装载质量,被配送货物是可混装的货物。

3. 每条配送路径的长度不超过车辆一次允许行驶的最大距离,配送中心有足够的资源以供配送,并且有足够的运输能力。

4. 各个客户需求和所在地均已知,每个需求点的需求由且仅由一辆车一次送货满足。

5. 满足总时间约束与时间窗口。必须在时间区间[ei,lj]访问点i客户,并允许在i处等待,车辆服务的总时间不能超过物流中心的时间约束。

6. 多个客户之间存在优先关系,必须在访问客户j之前访问客户i。

二、带时间窗VRP模型的建立

基于文献一文中的模型,并考虑配送系统是一个服务系统,所提供的服务必须能够让客户方便、满意。配送系统的运作成本必须和配送系统其他性能参数综合进行考评,单纯对成本进行评价是没有任何实际意义的。需要关注和努力的是:要在保证配送满足客户要求、提升客户满意度的同时,通过各种技术和管理手段,降低运作成本。因此,本文将建立改进的运输路径模型,在传统的车辆配送成本最小化目标的基础上,兼顾客户对配送时间的要求,使车辆等待和延误时间之和最小化。

式中K——车队规模,即总的车辆数目;

k——车辆数目(k=1,2,……,K);

N——有待访问的总的客户的数目;

O——配送中心;

Q——每辆车辆的容量,这里假设所有车辆同质,容量均为Q;

i,j——顾客数(i=1,2,……,N;j=1,2,……,N);

T——个很大的数字;

C——每辆车单位运距的运费;

t0——车辆从配送中心出发的时间;

e0——车辆可离开配送中心的最早时间;

ei——到达客户i处规定最早到达时间;

l0——车辆返回配送中心的最晚时间;

li——到达客户i处规定最晚到达时间;

dij——从客户i到客户j的距离;

pj——每个客户单位卸货量的卸载费用;

mi——客户i的货运需求量;

tki、tkj——第k辆车到达客户i、j处的时间;

tij——连接客户i和客户j的行驶时间;

si——客户i处的服务时间;

wi——在客户i的等待时间,wi≥0。

两个决策变量如下:

这个模型通用性很强,经过参数的不同设定,可以转换为其它组合优化问题的数学模型。

三、带时间窗VRP模型的遗传算法求解

在模型的处理上,根据本文提出的模型单位标量不统一的特殊性来选择权重系数变化法,将变化后的多目标函数经分析和试验得出各个子目标函数的数量级大小并确定权重,最后加权化为单目标函数用遗传算法求解。

1. 惩罚函数的引入。

在以往的对含有时间窗约束的车辆配送系统的研究中,所研究的成本大多仅包含行驶成本,但事实上,还包括其它成本(如装卸搬运成本),将时间窗约束转化为惩罚函数而体现在模型中。

式中c1——车辆在任务点处等待单位时间的机会成本。

c2——车辆在要求时间之后到达单位时间所处以的惩罚值(c1和c2的大小,要根据实际情况来定)。

2. 建立适度度函数。根据遗传算法中适应度函数的特点,需要将原目标函数式变化为:

式中A*,B*——变化后的目标函数值,取值范围为[0,1);

Amax,Bmax——分别是原始目标函数。

经过分析和实验发现,A*,B*经过处理后,A*的数量级一般是10-2,B*的数量级一般是10-1。

3. 用遗传算法求解带时间窗VRP模型。

本文取α=0.8,β=0.2,用遗传算法进行求解。在运用遗传算法求解后,验证了该算法易于理解,对问题的依赖性较小,对其求解的函数要求简单,实现起来简单高效,若参数选择的合理,收敛速度很快,但是遗传参数的控制对于算法的收敛速度影响很大,在参数选择方面有一定难度。虽然文中使用的是根据以往学者经验选定的参数,但计算表明最优解所在“代”数的稳定性不是很好,这也是以后需要进一步研究的地方。

四、结论

在传统的车辆配送成本最小化为目标的基础上,兼顾客户对配送时间的要求,建立了带时间窗的车辆路径优化多目标模型。在对模型的处理上,将两个量纲不统一的子目标函数除以各子目标函数的最大值后使其变成无量纲的函数,并通过权重系数变化法将各个子目标函数线性加权和作为多目标优化问题的适应度函数,使得多目标优化问题转化为单目标优化问题后再用遗传算法求解。

参考文献

[1]王惠:引入顾客满意度求解车辆优化调度问题.大连海事大学硕士论文,2006:1～13

[2]盛丽俊:带有时间窗的车辆路径问题的优化研究.大连海事大学硕士论文,2002:13～57

[3]牟燕妮:物流配送中路径优化的选择研究.沈阳工业大学硕士论文,2006:28～41

[4]周明孙树栋:遗传算法原理及应用.国防工业出版社,1999:130～137

航空快递的地面物流配送路径优化篇11

1 基于时间窗的车辆路径优化建模

1. 1 模型假设

假设配送对象为通用货物; 航空枢纽点与各站点之间的公路距离及各站点的货运量均已知; 航空枢纽点的运力能满足各站点的要求; 每条配送路径上各站点的货运量之和不超过配送车辆的总载重量; 每条配送路径的长度不超过配送车辆一次配送的最大允许行驶距离; 站点i的货物需要在时间窗口[ETi, LTi]内完成; 每个站点的货物必须送达, 且只能由一台配送车送货。为了建模的方便, 我们假设gi为第i点的货运量; k为配送中心内可进行服务的车辆个数; qk为每辆车的装载量; cij为任意两站点之间的运输费用。若两节点之间没有可达路线, 则相应cij值为无穷大; c1为早于ETi的惩罚因子, c2为晚于LTi的惩罚因子, 若事件不允许发生, 则两者的值取无穷大。

1. 2 模型的建立

地区航空枢纽点对其覆盖区域内的n个末端站点配送货物, 配送中心有m辆车。各站点在一次配送过程中必须且只能接受一辆车的服务, 即一个子回路对应着一辆车。航空枢纽点和各站点统称“节点”, 将它们从“0”到“i”依次进行编号。所有节点都要被服务且仅能被服务1 次, 每条路径都开始并终止于v0, 每辆车的负载不超过车辆最大载荷qk。ML表示车辆所允许的最大行驶路程。

根据上述假设, 目标函数及约束条件为:

其中, 表示任一线路的总运输量不超过车辆的承载量;表示一个需求点仅被一辆车服务;表示运输距离不得超过车辆的最大行驶路程。此外, 货物必须在[ETi, LTi]时间内送达满足如下条件函数:

2 基于VB编程带时间窗的物流配送路径优化求解

2. 1 基本思路

针对上述问题, 我们采用里程节约法进行求解。里程节约法, 是指一个航空枢纽点分别向N个站点配送货物, 在汽车载重能力及运行里程允许及满足限制函数的前提下, 每辆汽车的配送线路上经过的用户个数越多, 则配送线路越合理, 总配送距离越小。

2. 2 模型仿真

本文以某航空快递企业山东分区为例进行优化, 参数如下: 企业有效覆盖站点数为16 个; 配送中心车辆保有数为5辆; 单车最大载荷为3. 5 吨, 平均行驶速度为90 km/h, 最大行驶里程为1300 km。每个站点货物送达时间范围及最佳送达时间点T ( 单位: h) , 见表1。

2. 3 VB编程

基于VB编程求解以上问题, 结果如图1 和图2 所示:

由图2 可以看出, 该航空快递企业在山东分区的路线安排如表2 所示:

3 结论

随着航空快递业进入群雄争霸的阶段以及消费者对于时效性要求的提升, 速度已经成为航空快递企业最核心竞争力之一, 成为航空快递企业生死存亡的关键。提高地面物流配送速度已不能再回避, 航空快递企业必须提高认识, 从“上天”到“下地”全面发展, 提高整体实力, 从而在激烈的市场上求得生存和发展。