快递末端配送路线优化研究

1、题目：快递末端配送路线优化研究目录摘要3ABSTRACT4第1章 绪论51.1研究背景51.2研究意义71.3 国内外研究现状81.4研究内容9第2章快递末端配送现状分析92.1相关概念92.1.1快递概念102.1.2末端配送概念及特点102.1.3路线优化概念102.2快递末端配送路线发展的现状102.2.1快递末端配送路线现状102.3快递末端配送路线问题分析现状分析112.3.1社区单位的管理造成包裹投递困难122.3.2消费者由于繁忙或安全因素顾虑对末端投递有新需求122.3.3末端投递业务激增和成本上升12第3章 快递末端配送路线优化研究123.1模型建立123.1.1问题描述12

2、3.1.2问题假设133.1.3模型建立133.2问题规模和复杂度分析143. 3算法选择153. 3.1节约法的基本原理153.3.2节约法步骤163.3 算法应用163.3.1算法在模型中的应用163.3.2算法求解16第4章 案列分析174.1公司简介174.2案列介绍174.3案例求解184.4案例总结20第5章 总结与展望215.1总结215.2展望21参考文献：21致谢：22摘要物流市场成熟发展需要良好的末端物流配送支持。随着国内物流市场发展的日益成熟，对物流服务质量、物流时效性等提出了更高的要求，而解决末端配送难题是提升物流服务质量和物流时效的关键所在。国内物流业一直受困“最后一

3、公里”等末端配送难题，不少物流企业虽然网络健全，但是末端网点投入不足，管理混乱，消费者投诉增多，服务质量堪忧，无法满足物流市场规模不断增大对末端物流配送的现实需求。本文首先概述了末端配送的相关背景及概念，并深入分析当前国内外关于末端物流及快递企业物流的研究现状，总结了快递行业及其物流的发展现状，探讨了快递企业物流的主要内容和特点，分析了我国快递企业物流的现状及发展趋势；在建立快递末端配送路线优化问题的数学模型的基础上，构造了求解该问题的节约算法，并以某公司为例进行实验计算。计算结果表明，用节约算法进行快递末端配送路线优化，可以方便有效地求得问题的最优解或近似最优解。第1章 绪论1.1研究背景一

4、、快递物流的发展伴随着电商的迅速发展，快递业继续保持着年均50%左右的增速发展。与此前行业的抱团发展不同，在接连出台的政策支持下，今年快递企业各想各招，均想借资本的力量取得突破，上市成为各大民营快递企业的共同计划。从整体行业来看，大数据提升效率、出海下乡、兼并重组已成为发展趋势。快递业明年将迎来洗牌期，大量中小企业面临收购、淘汰的风险。 “互联网+”行动计划的提出，将推动移动互联网、云计算、大数据、物联网等与现代制造业结合。对快递而言，大数据应用将使电商企业与快递企业之间形成联动机制，“互联网+”与快递发生化学反应，互联网使快递更“聪明”，大幅提高快递效率，降低物流成本。国务院10月发布的关于

5、促进快递业发展的若干意见指出，鼓励快递企业发展跨境电商快递业务，加大对快递企业“走出去”的服务力度，在重点口岸城市建设国际快件处理中心，探索建立“海外仓”。同时，鼓励传统邮政业进一步加快转型发展，支持邮政企业和快递企业创新合作模式，充分利用现有邮政网点优势提高邮政基础设施利用效率。据了解，在跨境电商中随着“备货”模式兴起，通过仓储前置，传统集装箱海运的方式将得到青睐。传统快递企业和物流企业正在加大对保税仓、第三方转运等业务。二、物流配送的快速发展  20世纪90年代以来的实践证明，配送是一种非常好的物流形式。我国很多城市的物资部门建立配送站点，配送得到了很大发展。这样，彻底

6、改变了传统的流通模式和方式。过去物资流通部门等人上门买货，如今迈出家门主动上门送货，为生产企业配送急需的产品。通过本着筑造代理、配送、连锁相结合的新的流通形式，发展配送实现了质优价廉，中心实行统一集中进货，享受了生产企业的批量优惠，同时从用户和自身利益、信誉出发，严把进货关，保证进货质量。发展配送大大减少了生产企业的库存，实现了生产企业“零库存”的可能。而且，随着计算机网络的应用，逐步实现了配送中的流通现代化管理。同时，先进设施的使用也为用户提供了更加方便、快捷的服务，同时提高了流通企业的效率。在科技进步和管理技术创新的驱动下，物流产业经历了从量变到质变的过程，这种质的飞跃说明全球物流已经进入

7、供应链时代，而精细物流、闭环物流，对中国物流产业的发展产生了直接的影响。全球经济将进一步增长，伴随着经济增长的全球物流将会得到极大发展，发展中国家物流将迎来更大的发展机遇。21世纪物流的发展趋向归纳为信息化、网络化、柔性化、标准化、社会化等。中国物流应该把握供应链，提升核心竞争力。供应链是物流管理在深度和广度方面的扩展；制造业企业、物流企业都应重视供应链，供应链取代物流，不仅是理论的发展，更是时代的变革。从而使物流速度加快，准确率提高，库存减少，成本降低，以此延伸和放大传统物流的功能，为用户提供多功能、一体化的综合性服务。三、末端配送的快速发展末端配送是物流重要组成部分，是末端配送得以实现和发

8、展的重要保证。随着末端配送的迅猛发展以及生活节奏的加快，使得传统行业和消费方式正在发生深刻的变革，人们通过互联网检索商品信息，并通过电子订单发出购物请求，通过电子银行或者货到付款的形式进行支付，厂家通过快递的方式发货。末端配送物流体系主要包括仓储配货、干线运输和末端配送三个阶段。其中，末端配送问题即“最后一公里”问题，是整个网络购物活动中距离客户最近的环节，与消费者直接接触，末端配送质量的好坏直接关系到企业的物流成本以及消费者对整个物流服务的满 意程度。由于末端配送具有服务范围广泛、价值附加值较小、需求具有较大随机性 等问题，物流配送的“最后一公里”问题日益显著，快递企业在进行末端配送时抛弃了

9、传统的配送、集货分开进行的方式，采用集配一体化方式，这不仅有利于降低 企业成本、满足客户日益增加的需求，也能够节约资源、保护环境，造福人类社会。巨大的末端配送交易额产生了大量的物流需求，快递企业作为末端配送物流的主要承担者，在促进经济发展、方便社会交流、扩大就业、满足消费者需求等方 面具有积极作用。2014年2月通过邮政行业消费者申诉电话和申诉网站国家邮政局和各省(区、市)邮政管理局共受理消费者申诉39340件，其中涉及的快递业务 问题37761件，占总申诉量的96。其中消费者申诉的主要问题是快件延误、投 递服务质量及快件丢失短少等问题。要想妥善解决这一问题不仅需要国家统一调 控制定标准的行业

10、规范，也需要各快递企业通力合作、集成资源。1.2研究意义末端配送作为实现物流配送活动的最终环节，服务质量的高低与否直接关系到末端配送活动的成功或失败；与此同时，物流配送的运作成本和运作效率也决定了末端配送经济价值的多寡。本文对快递企业末端配送路线优化问题进行研究，具有一定的现实意义和社会意义。主要体现在： (1)综合考虑集货和配送业务、客户点对时间的要求以及对快递包裹大小和每日最大配送趟数的规划研究。(2)研究末端配送问题，不仅可以为末端配送企业充分整合现有的资源，设计合理、有效的末端配送方案提供参考，帮助电子商务企业以最大限度的增加快递末端车辆重载率、运输距离和运输成本，并且满足现代人们对于

11、时效性的严格要求，同时能够促进我国绿色物流的发展和和谐社会的实现。(3)根据末端配送的特点，分析末端配送系统需满足的条件，根据其对柔性的需求，提出利用末端共同配送系统解决末端配送环节存在的问题。(4)分析了我国目前末端配送存在的问题，为物流企业提高末端配送服务质量提供参考；若能广泛开展，可以在提高末端配送服务质量的同时，减轻工作人员的工作强度；也可以整合各电商配送企业的资源，提高物流设施设备的利用率，有利于提高企业服务能力；此外，末端配送的开展也有利于改善城市交通，带来社会效益。（5）配送合理化与否是配送决策系统的重要内容，配送线路的合理与否又是配送合理化的关键。选择合的理配送路线，对企业和社

12、会都具有很重要的意义。对企业来说：(1)优化配送路线，可以减少配送时间和配送里程，提高配送效率，增加车辆利用率，降低配送成本。(2)可以加快物流速度，能准时、快速地把货物送到客户的手中，提高客户满意度。(3)使配送作业安排合理化，提高企业作业效率，有利于企业提高竞争力与效益。对社会来说，它可以节省运输车辆，减少车辆空载率，降低了社会物流成本，对其 他企业尤其是生产企业具有重要意义。与此同时，还能缓解交通紧张状况，减少噪声、尾气排放等运输污染，对民生和环境也有不容忽视的作用。1.3 国内外研究现状末端物流是货物送达消费者的物流活动。电子商务的繁荣带动诸如快递公司这样的末端物流企业业务的快速增长，

13、末端物流效率越来越受到重视。为此各方都在不断寻找新出路并形成了一系列理论和实践观点。主要有以下三大类：（1）着眼于快递末端配送包裹大小及路径优化问题王良辉2以长安大学为例，以建立大学校园快递服务中心为基础，首先分析了大学校园快递末端业务的现状及问题，并有针对性的对这些问题提出大学校园快递服务中心这一创新商业模式。宗高勤4研究了共同配送站点和末端配送节点的可能形式，提出了电商末端共同配送可能的解决方案。陈娇5从电商的角度考虑，探讨了电商末端配送模式的优化对策，希望找到比较优化的电商末端配送模式。（2）物流末端配送现状及特点杨萌柯等6基于“互联网”背景下的快递物流发展现状和趋势分析,提出了电子商务

14、与快递物流协同配送模式以及城市快递末端的有限区域共同配送服务模式，通过构建以云平台为基础的城市快递物流协同服务网络，完善城市快递末端协同配送体系，从而有效解决“最后一公里”及“最后一百米” 配送难题。、郑捷扬等7分析国外电子商务末端配送模式，分别选取亚马逊河京东商城作为主要比较对象进行比较研究，分别从企业的战略、财务状况、库存水平等几个层面研究两家电商企业，分析两家企业在末端配送模式上的差异及在末端不同选择的原因，进一步比较对应的配送模式给各自带来的利益。（3）快递末端配送的发展趋势唐伶10提到：伴随城镇化加速发展和人们生活水平提高的同时，我国物流需求正在发生深刻变化。为迎合不同需求，物流末端

15、配送在整个流通过程中发挥着重要的作用，但其末端配送环节也引发了诸多问题。综上所述,末端配送作为一种专业化、社会化服务模式，体现了现代经济社会发展需要，是物流的一大进步。从整体和长远来看，物流末端配送所带来的经济效益是显而易见的，但对当前或短期影响却不一定是正面的，推广应用仍存在诸多困难，需展开不同层面的深入探讨。1.4研究内容本文的研究内容主要有：(1)搜集相关的资料，总结国内外关于末端物流及快递企业物流的研究现状；(2)通过搜集资料、文献分析，总结快递行业及其物流的发展现状；探讨了快递企业物流的主要内容和特点，分析了我国快递企业物流的现状及发展趋势；(3)针对快递企业物流里面的三个关键问题，

16、快递末端配送包裹容量问题、末端配送的路径规划和快递末端配送进行了研究；(4)最后以某公司为例，分析其物流现状，并提出建议和优化策略；(6)总结本文所做的工作，得出结论，并提出进一步研究的内容。第2章快递末端配送现状分析2.1相关概念2.1.1快递概念快递，是兼有邮递功能的门对门物流活动，即指快递公司通过铁路运输、公路运输、空运和航运等交通工具，对客户货物进行快速投递。在很多方面，快递要优于邮政的邮递服务。除了较快送达目的地及必须签收外，现时很多快递业者均提供邮件追踪功能、送递时间的承诺及其他按客户需要提供的服务。因此，快递的收费比一般邮递高出许多。2.1.2末端配送概念及特点末端物流配送是一种

17、服务，对于整个物流环节来说，末端物流是配送的最后一个环节。指的是送达给客户手中的物流，是以满足配送环节终端消费者为直接目的物流活动，可以实现“门到门”服务。具有使得客户简单方便领取货物，提高客户对快递公司满意度，扩大消费者群体的优势。末端配送作为公司最终直接面对客户的一种服务。服务的质量关系到客户的满意度，具有时效性、可靠性、沟通性、便利性、规模经济性的特点。2.1.3路线优化概念路线优化即在多条路线中寻找最优路线以达到规划后的要求包括线路最短，时间最短，以及成本最低。2.2快递末端配送路线发展的现状2.2.1快递末端配送路线现状快递企业在企业的人员规模以及资产规模和经营规模上处于先进地位，虽

18、然建立了完善的配送系统，但是对于末端配送问题也是比较头疼，所以快递企业大部分通过寻找其他途径以求解决此问题，而各个企业根据自己的业务范围以及公司特点采用了不同的方法，大致可以分为以下三点：（1）通过网络化信息平台加强末端配送措施2013年申通通过加盟授权品牌的形式，在全国个省市建立了庞大的快递物流服务网络体系，其业务内容包括信息采集与传递、市场需求研究与市场开发、企业委托的第三方物流配送、快递包裹投递配送等。此外，申通还将不断完善信息系统与信息基础设施建设，完成网络化与信心化改造，在巩固传统快递业务的基础上，进军电子商务物流与3PL 物流领域。2013年5月28日，阿里巴巴集团、银泰集团联合复

19、星集团、富春控股、顺丰集团、三通一达（申通、Y公司、中通、韵达），宅急送、汇通，以及相关金融机构共同宣布，“中国智能物流骨干网”(简称CSN)项目正式启动，合作各方共同组建的“菜鸟网络科技有限公司”正式成立。利用先进的互联网技术，建立开放、透明、共享的数据应用平台，为电子商务企业、物流公司、仓储企业、第三方物流服务商、供应链服务商等各类企业提供优质服务，支持物流行业向高附加值领域发展和升级2011年初阿里巴巴集团正式推出物流信息管理系统“物流宝”，其核心在于物流仓储资源的数据化分析和管理能力，调配第三方物流资源。物流宝又称“天网”。菜鸟网络：其核心主要在于建设仓储设施网络，初期仓储设施的选址主

20、要在靠近生产基地、交通设施的地区。菜鸟网络又称“地网”，在未来5-8年内打造一张遍布全国的物流基础设施网络，让全国任何一个地区做到24小时内送货必达。（2）通过吸收社会运力发展众包快递配送2016年5月19日，Y公司将重点寻求最后一公里的终端配送业务，开始突破现有网点加盟送货上门模式，放开网点限制，将社会化运力网入其中。比如夫妻店、创业大学生、下岗职工等均可申请成为网点下一级配送站点，布局毛细血管配送网络。（3）通过路径规划优化末端配送2010年，刘庆元和杜文贞将最短路问题与Are GIS软件相结合，通过VRP模型将最短路反映到Arc GIS软件中，直观反映出配送的最短路径。2012年，王华研

21、究了一类基于图论的最短路径问题，并通过算法间的比较进行了验证。同年，王辛岩和李庆华将GIS与最短路问题相结合，详细阐述了通过GIS实现最短路径的方法与步骤。2.3快递末端配送路线问题分析现状分析电子商务和网络交易的大力发展，客户对快递企业的送货速度以及服务质量要求越来越高；而快递企业因其管理信息化还不成熟，为客户提供专业化的快递服务的目标难以实现，同时不能保证在第一时间使所有该业务相关部门同步迅速地行动起来，这就无法最快最好地满足客户个性化的服务体验需求，也无法保证货物能按客户的需求快速送到指定地点。出于安全考虑，中高档社区与高校一般都不让快递员进入其内部送件，一般只能把快件送到校门口或社区保

22、安室。但由于没有专人管理，收件人取件时间不固定，造成快件安全无法保证。或者快递人员到达门口再把快件堆放在在校园社区周边的空地上，集中发短信通知客户在预定的时间内自提。大量快件包裹散乱堆放在人行路或草地上，严重影响了市容市貌，客户提货时的秩序也相当的混乱，时常出现由于收件人无法在快递服务人员规定时间内提货而需要二次配送，严重影响了快递服务的效率和质量。快递人员服务态度也存在很大的问题，今年来不断收到客户对快递员的投诉。网上也充满了客户对快递员服务态度的抱怨。根据以上几个现状分析得出快递末端配送现状存在以下三个问题：2.3.1社区单位的管理造成包裹投递困难很多快件投递的最终地址包括居民小区、单位大

23、院、写字楼、学校等地方。而很多社区、单位出于安全和管理的要求，禁止快递员进入，这就给快件包裹的交付造成一定的困难。2.3.2消费者由于繁忙或安全因素顾虑对末端投递有新需求很多消费者填写的收件地址是家庭住址，而派件的时候很可能收件人正在上班；也有一些收件人填写的是单位地址，派件时也可能会遇到正好不在单位的情况。这时如果没有一些代收方案，就给包裹的最终投递完成造成困难。此外，电商物流安全问题随着网购量爆发式的增长越来越突出。安全隐患也是不容忽视的问题。2.3.3末端投递业务激增和成本上升末端投递业务激增和成本上升，使得电商和快递公司需要创新的服务方式。据国家邮政局数据，目前我国快递规模世界第一。2

24、008年至今，快递业务量由15亿件增至206.7亿件，平均年复合增长率43.9%。2015年我国规模以上快递业务收入总额接近2800亿元，7年间年复合增长率达到31.4%。巨大的业务增量一方面促进了快递公司的成长与发展，另一方面也使得传统单一的上门投递方式难以满足需要。第3章 快递末端配送路线优化研究3.1模型建立3.1.1问题描述一个大区域下分为若干小区域，每一快递员对应一个小区域的送货服务，同一配送区域的客户由快递员同次送货，对车辆要求一次完成同一区域所有客户(需求点)的送货任务，送货完成后可以回货源点补货，再配送其他区域，形成路径优化问题。3.1.2问题假设（1）被配送的是已知的一种或者

25、几种物资；（2）各个客户的所在地和需求都知道；（3）快递员从配送站点到各客户及各个客户点之间的运输距离已知；（4）快递员配送的车辆都有一定的限制，不能超载；且不考虑容积充分利用，保证包裹能装进车辆就行；（5）每个客户相当于一个节点，仅配送一次，快递员遍历各个节点完成末端配；（6）假设快递员在每个节点的平均配送完成时间是固定的1分钟，快递员在整个配送过程中卸货总时间固定，不随决策变量变化，固目标函数也不受影响；（7）假设快递员配送过程中平均行驶速度一定，则求快递员完成末端配送的最短时间，即为求得一个遍历各个配送点的最短路径的方案；（8）快递员提前通知客户取件，对于当天部分不能完成配送的货物遍历完

26、成各个节点后将货物带回，归入第二天的配送，继续完成前述遍历配送；（9）假设平均每件快递重量为1.5kg；3.1.3模型建立末端配送路径优化问题描述为：配送站点仅有一位快递员完成运输任务，但是由于车辆载重有限，无法一次完成所有配送点的配送，故需要规划配送区域，配送完一个区域的客户后回到配送站点装货再次进行配送，直到将所有配送点配送任务完成。建立单车多任务配送模型，具体思路如下：考虑到现实路网的复杂性，对快递末端配送路径优化问题建立以时间最短为优化目标的模型。令dij表示节点i到节点j的直达距离（i，j=1，2,3，N）。若从i到j无直达路径，则用dij=表示。令快递员配送的的客户集合为N(其中0

27、代表快递配送站点，配送节点的个数为n)。变量tij（Ti） (其中i，jN)表示快递员从需求点i经过用时最短路径到需求点j所用的时间（不包含卸货时间）。客户i需求为qi。R为配送路径集合。qmax为车辆最大装载量。定义决策变量Ti (i，jN；ij；rR)：如果车辆在路径r中为i点完成服务后下一服务点j时，则xrij=1；否则，xrij=0。则单车多任务末端物流配送路径问题数学模型如下：Min Z =（tij（Ti）xrij ）+n （1）-tij（Ti）表示快递员从需求点i经过最短路径r到需求点j用的时间；-xrij：n个节点间有C2n路径，xrij=1表示快递员经过此路径，xrij=0表示

28、快递员不经过此路径；-n：假设快递员在每个节点的平均配送完成时间是固定的1分钟，n个节点总卸货时间为n；xrij=xrji （2）-式(2)是平衡条件，即快递员在某次配送任务到达某节点次数与离开该点次数相同；1=xrji /0 （3）-式(3)表示对每个节点的配送为一次且仅为一次；-1 xrji，/0 （4）-式(5)确保配送回路通过配送站点；qiqmax （5）-式(6)表示每条线路上的节点货物需求总量小于车辆的最大载运量。3.2问题规模和复杂度分析近几年，我国快递行业发展迅速，而且全国范围内形成了点轴面的系统。而本文研究的是对于快递点的配送路径优化，相对于轴与面的路径优化问题只是研究配送路

29、径最短，配送成本最低，顾客对快递的送达时间没有什么具体要求。且一个快递点单次配送顾客数并不多，且货物量不大，配送规模较小。每个快递员都有自己的区域，收件派件到完成就好，每个人区域不是很大，件不是很多，每天多的时候八九十件，少的时候三四十件，所以问题规模较小，且问题复杂度较低3. 3算法选择快递末端配送即为快递员“最后一百米”直接面对客户群体的配送：只有一个快递员，不需要考虑时间的影响；工作时间依照快递员个人安排，相对随意，因而也不考虑车辆及成本的影响；货物确定；客户群体稳定，规模较小；车辆路径问题主要解决方法分为：1.精确优化方法；2.启发式方法。由于启发式算法是一宗逐次逼近的方法，虽然不一定

30、得到最优解，但是可以高效率地得到具有较高精度的解，而且也易于考虑各种实际问题。因此，本文将用启发算法的节约算法进行求解。3. 3.1节约法的基本原理节约法是由Clarke和Wright于1964年提出的。该方法的核心思想是依次将运输问题中的两个回路合并为一个回路，每次使合并后的运输距离减小的幅度最大，直到达到一两车的装载限制时，再进行下一辆车的优化，直到选出最佳配送路径的方法。如图所示，由物流中心P向两个客户A、B送货，P至A、B的最短距离分别为l1和l2，A、B间的最短距离为l3，客户A、B的货物需求量分别为q1和q2。对上述问题，最简单的配送方法是用两台车辆分别对A、B两个客户运送所需货物

31、，然后各自返回物流中心。使用该种配送路径方案时配送车辆的走行总里程为： 1=2(l1+l2)如果改为由快递员车辆向A、B两个客户巡回送货(设q1+q2配送车辆的载重量)，则配送车辆的走行总里程为：1=l1+12+13 (1.1)后一种配送方案比前一种配送方案节约的车辆走行里程为：l=2(1l+12)-(ll+12+13)=ll+12- 13 (1.2)式(1,4)称为节约量公式，从图形看，它等于三角形的两个邻边之和减去对边的差。如果在物流中心P的供货范围内还存在着第3、4、5、L个客户，在配送车辆载重量允许的情况下，可将它们按节约量的大小依次连入巡回线路，直至车辆满载为止。余下的客户可用同样的

32、方法确定巡回路线，另外派车。3.3.2节约法步骤基于节约里程法的基本思路，在配送网络中尽量使运输车辆多载，尽量节约总配送时间和总配送里程。具体步骤如下：（1）：做出最短距离矩阵。即根据配送网络图中物流中心与客户之间以及客户相互之间的距离，计算出物流中心与各客户之间以及各客户相互之间的最短距离矩阵。求配送网络顶点间的最短距离时可采用求最短路的算法，（2）：编制节约里程表。即根掘物流中心与客户问及各客户相互问的最短距离矩阵，利用节约量计算公式计算出客户相互间的节约里程。节约里程的计算结果有正有负，当节约里程的计算结果为负数时，无实际意义，取其节约量为0，将节约里程填入节约里程表。（3）：编制节约里

33、程顺序表。即将节约里程表中的节约里程按由大到小的顺序排列，然后填入节约里程顺序表。（4）：制定配送路线。即根据节约里程顺序表中节约里程的大小顺序和物流配送车辆调度问题的约束条件，逐渐组成配送路径图。3.3 算法应用3.3.1算法在模型中的应用节约法是一种启发式方法，它属于逐次逼近法的一种，用该方法不一定能求得末端配送路线优化问题的精确最优解，但可以高效地得到问题的近似最优解。该方法具有计算步骤简单，计算速度快，且易于考虑各种实际问题的优点。该方法的缺点是未组合点零乱、边缘点难于组合以及有时解的质量不高等。3.3.2算法求解 本文研究的末端配送是对一系列给定的顾客（取货点或送货点），确定适合的配

34、送车辆行驶路线，使其从配送站点出发，有序的通过他们，最后回到配送站点。在满足一定的约束条件下（如车辆容量限制、顾客需求量、交发货时间等），达到一定的目标（如里程最短、费用最少等）。属于单配送站点配送规划问题。已知快递员P0向n个客户Pj配送货物，其配送路线网络、配送站点与客户之间的距离如下图所示，快递员装载量有限以及一天运输次数的限制，利用节约里程法制定最优配送方案。客户与配送站点距离表客户配送站点P12n1d1p0D12d 1n2d2pd210d 2nnDnpd n1d n20（1） 根据节约公式Sij=dj1×2+di2×2-(di1+dj1+dij)算出节约值，求出各

35、点节约距离。（2） 根据算出的Sij节约距离进行排序。选择节省路程最多且满足配送限制条件的路径的为最优解。（3） 以此为例，计算其他路径的节省路径的节约值，公式与计算方法与上式相同在此省略。（4） 对于当天由于客户个人原因不能收取货物的，将其带回，列入第二天的配送中依照上述方法进行再次配送。第4章 案列分析4.1公司简介Y公司成立于2000年5月28日，是国内大型民营快递品牌企业，致力于成为“引领行业发展的公司”为奋斗目标。公司拥有10个管理区、58个转运中心、5100余个配送网点、5万余名员工，服务范围覆盖国内1200余个城市。公司开通了港澳台、中东和东南亚专线服务。公司立足国内，面向国际，

36、致力于开拓和发展国际、国内快递、物流市场。公司主营包裹快递业务，形成了包括同城当天件、区域当天件、快递时效件和航空次晨达、航空次日下午达和到付、代收货款、签单返还等多种增值服务产品。公司的服务涵盖仓储、配送及特种运输等一系列的专业速递服务，并为客户量身制定速递方案，提供个性化、一站式的服务。4.2案列介绍本案例依据于Y公司某次配送为例子，并加以简化，某快递点P0要配送10个客户P1P10，快递点与各客户以及各客户之间位置距离如下图所示：两点间连线上的数为两点间的距离（单位：公里），各配送点的快递量见表一，快递由快递点统一收取并配送，快递点只有一位快递员，且每次最多可以配送20kg的包裹。假设送

37、到时间均符合客户要求。 图1配送网络图表1：包裹需求量 单位：kg顾客P1P2P3P4P5P6P7P8P9P10合计重量3.243.242.41.64.843.22.432.84.3案例求解用节约里程法进行求解，其步骤如下：第一步：从配送网络图中计算出快递点P0到各个客户及各个客户之间的最短距离，并做出最短距离表（见表2）。表2 最短距离表P0P1P2P3P4P5P6P7P8P9P10P00109788834107P10491418181314114P2051014171213158P30591510111713P4061311121815P50710121815P60681715P70211

38、10P80911P908P100第二步：由最短距离表，利用“节约里程”计算出各个客户配送点之间的节约里程，做出节约里程表（见表3），计算结果有正有负，节约里程为负数时，无实际意义，在表内写0。表3节约里程表P1P2P3P4P5P6P7P8P9P10P1015840000913P20117300048P3010600001P401030000P5091000P605410P70520P8050P909P100第三步：将节约里程由大到小顺序排列，列出节约里程排序表（见表4），以便尽量使节约里程最多的点组合成一个区域进行装车配送。顺序排位连接线节约里程顺序排位连接线节约里程1P1-P21513P6-

39、P752P1-P101313P7-P853P2-P31113P8-P954P4-P51016P2-P944P3-P41016P1-P446P1-P9916P6-P846P5-P6919P2-P536P9-P10919P4-P639P1-P3821P7-P929P2-P10822P7-P10111P2-P4722P5-P7112P3-P5622P6-P91第四步：根据节约里程排序表和快递员车辆在中等约束条件，渐近绘出如图2所示的配送路线图。从配送路线图可以看出，依次确定的三条配送路线配送均符合配送站点的约束条件，需要快递员配送3次：（1）路线1：P0-P10-P1-P2-P3-P4-P0；3.2

40、+4+3.2+4+2.4=12.8kg<20kg;总路程=6+2+5+5+4+4+7=33公里；（2）路线2：P0- P5- P6- P7- P8 - P0；2.4+1.6+4.8+4=14.8kg<20kg； 总路程=8+7+6+2+4=27公里；（3）路线3：P0-P9; 3.2kg<20kg;总路程=10公里；三条路线总路程=33+27+10=70公里；4.4案例总结本章案例讨论了实时路网下末端物流配送问题，建立了基于实时路网的单车多任务路线优化模型。用节约法对快递末端配送路线进行优化后，减少了线路重叠、货物的疏散，使配送更加集中，更有效率；使营运时效指标得到改良，提高了客户满意率。但是该方法只适用于单车多任务路径优化问题，对于规模较小的可以一一枚举；但并不适用于大规模末端配送路线优化问题，因而末端配送路线方面的问题仍然有待研究。第5章 总结与展望5.1总结（1）对我国快递行业发展现状及末端配送发展现状进行分析企业降低物流成本、提高利润的主要手段（2）通过TSP问题求解算法的