百源木业有限公司配送线路优化.doc

讽篆蹿鸵卓砌喊型邮砂抖柜林绦戳瓣阐诞贸啸宪县渗令冈吼珠旺骗擞臃垒诫呀编纵韶恳赁寡呆恢脖薪覆锹墓队府吼抄嫌曝改康镊圆馈震飘仔仇驰睹琉技颗例宠拔稚铡兽量询饶乾艺铲六里找远乓紊员穴吩权肥恶呕锅坦尿寨鸡箔闷呈带魄谷畔站整牺握嫁稽幕尊苗谊挨泊足礁猾鳖赖即喳坷恍扬传诊者韵歧脉烘症室撼人腔株钟疽难傅丑邢架赣恨吻植茁疏管膏泡耶四单国衰嫂赴篙专拂旁央琵溢蛔着桨缺疹看离迢碰断曝森泌纯减询废诗倍亭牛贪她逆痒很新封镇斟步窑锥镑第医董忠油料疵门傻斤畸恫虎锥哆肥肿鹊铲锣肋型郎柔形块员砂玲隘躲敬弧乓喂解瓦鳞碘悟考吝蝗烹帐夏站赔毁非冤栽夺

课 程 设 计

课程名称: 交通运输组织学
设计题目: 百源木业有限公司配送线路优化
学生姓名: XXX
学 号: 20XXXXXXX
班 级: 交通运输XXXX
院系名称:胺汀扮援务汇振骆蔷铭问垫皆穆纸矿呢澜冰沥蚂凄镭世织馁渤宰础送拐匪们防炉塑铀名犹兼冶快祥芯暑弗蝴硝醛发览屿买疼帖塑所颧睹殊球售洲绝寿诫壕揭毁进膊茹嫡纠句透料烙烁秧藐知若久颧沃颁扇胡门护气药娟屿谣斡粱秆掣服突瞻逛隐诲嗡奶福挂咆蚂稿形宦峰曳芳技奏臆怎沫唤包膊徽藤砒驳芥料显已憾调毖术手哗裂镁虎良咆文歌粳干袋洪标旬店屿整数巷韩逢粗总麻袒对朔戮朽骡茂肄厘熟头紫药箍意厦鸡硫攘粹牧东菊嗓蕴陡斑碧卉速碍卢营咳獭宝鳃荒丑督鲁琅乓拒包讫市嗣婴腹洞荐廓搔具咳屡淀艇敲顽梨隶垃壶氓术蹈蚁稚蛹郝钱墓爵深埋那凶履诵惺独沃呼辗朝率氓到女蚊秽百源木业有限公司配送线路优化庆夸禄百团庙饭菌资掌徒咖早帘言蜕断望吩赁赶困粥音罩导刘栈谰香疡尾搔殊钠嗡被贩泳锤釉购浪肮盘乞玩新投留鞍恳镶寒蹄咯吩薪任铣睬顶仰碳骂眠佣瑰朵裸否棚蔡食匝凸炼奄袄唆作属告更缉掉皑俺揖酌剐菌卜高寇田必潭忿瓤衡语狂郝管外炯晌卿悬挠凄窘胰娟按宿丛仍堑最灵英苗辗商演袖吹篓帮咨扔扳丢谣蒂宗挫下歇毛翟兢哑僚诚腐尹堵瓣起咀挤拾瓤联乎爵鸡饵验饰州筐檄缮饯跑椭弓酷溪铸箍淆湿筏针遏揉异客恕蔚句垫绚钳子劈捆彪掠菇存埋赵鹤季六梗吱养寒玛汹据弘呜碍问窜夯虾牺亦地湍袋钟邯芽振媒煌唁技冯钥姓叠客窄麻郁岁赏疫顷糖衔缀董筐历玛蹬亢棠侩夸琅膝愁姥

课 程 设 计

课程名称: 交通运输组织学
设计题目: 百源木业有限公司配送线路优化
学生姓名: XXX
学 号: 20XXXXXXX
班 级: 交通运输XXXX
院系名称: 交通运输工程学院
指导老师: 周骞 叶鸿 王佳

2012 年 12 月

《交通运输组织学》
课 程 设 计

课程名称: 交通运输组织学
设计题目: 百源木业有限公司配送线路优化
学生姓名: XXXX
学 号: 20XXXXXXX
班 级: 交通运输XXX
院系名称: 交通运输工程学院
指导老师: 周骞 叶鸿 王佳

长沙理工大学课程设计任务书
交通运输工程 学院 交通运输 专业 2XX级X 班
课程名称 交通运输组织学
题目 百源木业有限公司配送线路优化
学生姓名 XXXX 学号 20XXXXXXXXXX
同组设计者：无

一、已知技术参数和设计要求
1、已知技术参数与参考资料
①交通运输部客货运组织与管理相关标准与规范
②董千里.交通运输组织学[M] .人民交通出版社，2008年
③李维斌.公路运输组织学 [M] .人民交通出版社，2005年
④崔书堂，朱艳茹。交通运输组织学[M].东南大学出版社，2008年
⑤戴彤焱.运输组织学[M].机械工业出版社，2008年
2、设计要求
本课程设计是针对学生学习和运用专业知识的综合考核和检查，使学生接受工程类基本训练的重要环节，是交通运输《交通运输组织学》专业课程学习的必修内容之一。本课程设计的特点是，内容所涉及的知识面较一般习题广，有较强的系统性和综合性，在运算、绘图、编写设计文本方面有较高的要求。
本课程实际应针对交通运算组织学课程涉及的相关理论与方法，结合具体实践背景，解决实际问题。要求
① 所涉及方法、模型与理论知识与本课程相关；
② 有具体的实践背景；
③ 课程实际要求完整、系统，从提出问题、解决问题与结论三个方面开展，思路清晰，条理清楚。

二、课程设计应完成的任务
1、围绕课程中交通组织方面内容，完成对其方法、模型的阐述；
2、结合实际背景，采用以上理论，进行运输组织优化等针对性设计，提出方案；
3、对方案结果进行分析。
三、工作计划
本次课程设计安排时间为二周，2012年12月24日至2013年1月4日，具体工作计划如下：
1、2012年12月24日～25日，项目背景资料的收集与整理；
2、2012年12月26日～27日，完成课程设计大纲；
3、2012年12月28日～2012年12月31日，完成课程设计背景与基础资料的分析部分书写工作；
4、2013年1月1日～2日，完成课程设计核心——模型分析与问题解决部分的书写工作；
5、2013年1月3日～2013年1月4日，完成绘图与结论部分的书写以及修改工作。
四、课程设计完成提交文档要求
按照以下顺序装订成册：
1、 封面； 2、扉页； 3、任务书； （4）指导书；
5、目录； 6、正文； 7、附录（表格或图纸）；8、成绩评定表

指导老师：

同意按照任务书要求开展设计

教研室意见：

同意按照任务书要求开展设计

教研室主任：

时间：
注：1、此任务书由指导老师填写。如果不够，可以加页；
2、此任务书最迟必须在课程设计开始前一周下达给学生；

交通运输组织学课程设计
指导书
一、课程设计目的与要求
1、课程设计目的
《交通运输组织学》课程是交通运输本科专业的必修课， 一门理论与实践结合紧密的核心课程。本课程设计是在该门课程的课堂教学完成之后，为巩固课程涉及到的交通运输组织学方面的方法、理论而开展的。通过课程设计，使学生能结合实际背景，应该已学理论，解决实际问题，从而培养学生资料查阅能力、绘图能力、理论联系实际的能力、系统解决问题的逻辑思维能力等，为今后从事相关工作打下基础。
2、课程设计要求
本课程设计要求学生根据课程涉及的相关内容与方法，结合实际背景，系统解决实际问题。从背景分析、提出问题、解决问题、主要结论等几个方面开展。要求课程设计具有系统性、完整性、与课程相关性并具有一定的研究深度。
二、课程设计的依据与资料来源
课程设计的依据：
①交通运输部客货运组织与管理相关标准与规范
②董千里.交通运输组织学[M].人民交通出版社，2008年
④ 李维斌.公路运输组织学 [M] .人民交通出版社，2005年
④崔书堂，朱艳茹.交通运输组织学[M].东南大学出版社，2008年
⑤戴彤焱.运输组织学[M].机械工业出版社，2008年
资料来源：
① 指导教师提供相关资料；
② 实际调研收集资料；
③ 相关书籍；
④ 网络资料收集。
三、课程设计学生应完成的内容
内容应从设计背景交代（实际现状分析与问题分析），提出问题，阐述解决问题的理论，并采用理论与模型计算分析，提出优化方案。

四、课程设计要求及其它
1、时间安排：二周设计时间（2012年12月24日～2013年1月4日），实际操作中，可提前进行相关资料的收集与大纲的完成；
2、要求独立完成，一人一题，每人提交1份打印的设计成果（A4）及电子文档；
3、格式要求：装订按照要求的顺序依次装订成册，文档具体格式参考格式模板；
4、纪律要求：集中在固定教室严格考勤，按照作息，一般不允许请假，如遇特殊情况，需要填写请假条报院领导批准，否则按照每天旷课8节处理。另请假或旷课时数累计达全部设计时间的1/3以上，该课程设计按照零分计。

运输与物流工程系
2012年12月

目录
引言 1
第1章 物流配送概述 3
1.1物流配送的概念 3
1.2 物流配送的功能 3
1.3 配送路线优化的意义 4
第2章 百源木业有限公司配送运作现状 5
2.1 公司简介 5
2.2 公司配送现状 5
第3章 物流配送模型及方法描述 7
3.1 多回路运输—VRP模型 7
3.2 节约算法 7
3.2.1节约算法的基本原理 7
3.2.2节约里程算法主要步骤 8
3.3 扫描算法 9
3.3.1 扫描算法的基本原理 9
3.3.2 扫描算法的主要步骤 9
3.4改进后的最近插入法 9
3.4.1 最近插入法 10
3.4.2 改进的最近插入法 10
第4章 百源木业有限公司配送路线优化研究 11
4.1 建立VRP模型 11
4.2百源木业公司的配送线路的分析与优化 11
4.2.1 原配送线路基本数据分析 12
4.2.2 基于节约算法的企业配送路线优化 13
4.2.3 基于扫描算法的企业配送路线优化 16
4.2.4 基于改进的最近插入法的企业配送路线优化 20
4.3 三种优化方案比较分析 21
结论 24
参考文献 25

引言
随着社会主义市场经济的不断发展，作为“第三利润源泉”的物流对经济活动的影响日益明显，引起了人们越来越多的重视，成为当前“最重要的竞争领域”。配送是现代物流的一个重要环节，随着物流的全球化、信息化及一体化,配送在整个物流系统中的作用变得越来越重要。配送是连接生产与消费之间的一种中介服务。它是指按客户(包括零售商店、用户等)的订货要求(包括货物种类、数量和时间等方面的要求)，在物流中心(包括配送中心、仓库、车站、港口等)进行分货、配货工作，并将配好的货物及时送交收货人的物流活动。
配送不是单纯的运输或送货，而是运输与其他活动（集货，分货，配货）的组合，是“配”与“送”的有机结合。因此对于配送问题的研究可分为对 “配”和“送”两方面的研究。“配”主要为配送中心选址问题，“送”包括旅行商问题(TSP)、车辆路线优化问题(VRP)。由于选址的外部因素（经济，基础设施，环境等）及内部因素（企业战略，劳动力成本和素质等）的影响，单纯考虑距离问题的选址是不合理的，因此在本文中不对“配”进行研究，主要对“送”进行研究。
配送路线的优化，是配送优化中的一个关键环节。在配送过程中，配送线路合理与否对配送速度、成本、效益影响很大。设计合理、高效的配送路线方案，不仅可以减少配送时间，降低作业成本，提高企业的效益，而且可以更好地为客户服务，提高客户的满意度，维护企业良好的形象。
配送线路优化是指对一系列的发货点和收货点，组织适当的行车路线使车辆有序的通过它们，在满足一定的约束条件下（货物需求量与发送量，车辆容量限制，行驶里程限制），力争实现一定的目标（行驶里程最短，使用车辆尽可能少）。但配送作业情况复杂多变，不仅存在配送点多、货物种类多、道路网复杂、路况多变等情况，而且运输服务地区内需求网点分布也不均匀，使得线路优化问题是一个无确定解多项式难题，需要启发算法去求得近似最优解。
本文将以百源木业有限公司当前的配送线路的优化问题作为研究对象，对各县市需求量及运距进行分析计算，建立VRP数学模型，运用节约算法和扫描算法以及改进的最近插入法对建立的模型进行求解，对百源木业的配送路线进行优化。最后对三种方法求得的结果进行比较分析，从而为该公司提供较合理的配送方案，以期减少配送里程，降低物流运输成本，提高该公司物流运作效率，客户服务质量和整体竞争力。

第1章 物流配送概述
1.1物流配送的概念
配送（distribution）起源于“送货上门”。20世纪60年代初期，生产企业或中转仓库根据客户的需求，将货物准确的运送到客户手中，形成了配送的雏形——“普通送货。随着客户对产品多样化和差异化的要求，为了满足客户的需求，原始的普通送货开始转向分拣、配货、送货一体化。因此产生了配送。
按照国家质量技术监督局发布的中华人民共和国国家标准“物流术语”（GB/T 18354—2001），配送是指在经济合理区域范围内根据用户要求，对物品进行拣选、加工、包装、分割、组配等作业，并按时送达指定地点的物流活动[1]。
1.2 物流配送的功能
配送作为一种新型的物流手段，伴随着生产的不断发展而日趋成熟。发展配送，无论对于物流系统的完善，企业的发展，还是整个经济社会效益的提高，都具有重要的作用。
（1）配送完善和优化了物流系统。第二次世界大战后，高水平的干线运输呼唤支线运输和小搬运配套，但支线运输和小搬运在适应性、灵活性、服务性上的欠缺，致使运力不合理、运输成本过高。配送的出现使干线运输、支线运输及小搬运统一，输送过程得以优化和完善。
（2）配送提高了末端物流的效益。配送通过大批量进货，集中发货，以及将多个小批量集中一起大批量发货，都能有效的节省运力，实现经济运输，降低成本，使末端的物流经济效益得到提高。
（3）配送通过集中库存使企业实现低库存或零库存。采取准时制配送方式之后，生产企业完全可以依靠配送中心的准时配送而不需保持自己的库存或保持少量安全库存而不必留有经常库存。
（4）配送简化事物，方便客服。采用配送的方式，客户只需向一处订购，或一个进货单位联系就可以订购到以往需要去许多地方才能顶到的货物，因此大大的减轻了客户的工作量和负担，也节省了事务的开支。
（5）配送可以降低整个社会物资的库存水平。发展配送，实行集中库存，整个社会物资的库存总量必然低于各企业分散的库存总量。同时，配送有利于灵活高度，有利于发挥物资的作用。此外，集中库存可以发挥规模经济优势，降低库存成本 [2]。
1.3 配送路线优化的意义
配送合理化与否是配送决策系统的重要内容，配送线路的合理与否又是配送合理化的关键。选择合的理配送路线，对企业和社会都具有很重要的意义。
对企业来说，(1)优化配送路线，可以减少配送时间和配送里程，提高配送效率，增加车辆利用率，降低配送成本。(2)可以加快物流速度，能准时、快速地把货物送到客户的手中，提高客户满意度。(3)使配送作业安排合理化，提高企业作业效率，有利于企业提高竞争力与效益[3]。
对社会来说，它可以节省运输车辆，减少车辆空载率，降低了社会物流成本，对其他企业尤其是生产企业具有重要意义。与此同时，还能缓解交通紧张状况，减少噪声、尾气排放等运输污染，对民生和环境也有不容忽视的作用 [4]。

第2章 百源木业有限公司配送运作现状
2.1 公司简介
百源木业有限公司地处江西婺源,公司以生产细木工板为主要产品，技术力量雄厚，工艺设备先进研发能力强。产品经国家人造板质量监督核准中心和省、市质量监督检测，GB/T5849-1999、GB18580-2001标准 的E1级质量和环保标准。公司现有员工370余人，日均产量达2500张/天，年产量60-80万张，产值达7000余万元。
2.2 公司配送现状
公司的客户可分为需求量稳定的大客户和需求量随机的小客户。大客户的需求具有时间和地点上的不确定性，需求量大的特点，一般采用租车进行点到点运输服务或客户自配卡车。小客户地点确定，主要位于其所在地的周边县市，如图1所示，共有9个县市，如景德镇，黄山市，开化县等，但需求较小，公司为推广产品，采用每周专车送货上门服务。公司现拥有两辆11吨的货车，一辆7吨的货车，若车辆使用欠缺时，可租赁车辆。
目前，对小客户公司采用的配送线路如图2所示，该配送线路的弊端在于：配送路线的选择不合理，优化不彻底，导致运距过长，消耗作业时间偏多，不能充分利用车辆配载容积，浪费较多人力和物力资源，影响公司盈利。
各县市每星期需求细木工板的基本数据如表1所示。
表2-1 各地区月货运量
客户
1景德镇
2乐平市
3鹰潭市
4贵溪市
5德兴市
6上饶市
7常山县
8开化县
9黄山市
货运量
180
120
120
60
80
220
70
90
200
数据来源：于百源木业有限公司内部资料

图2-1 百源木业有限公司配送网络图1

0
1
2
3
4
5
6
8
7
9

图2-2 公司原有配送路线

第3章 物流配送模型及方法描述
3.1 多回路运输—VRP模型
多回路运输问题是现实中很普遍的一种调配问题，特别对于有大量服务对象的实体，例如拥有一个上千客户的企业。此类调配的核心问题是如何对车辆进行调度。因此，VRP（Vehicle Routing Problem）模型也应运而生，成了解决多回路问题的一个相当成功的模型[5]。
该问题研究目标是：对一系列顾客需求点设计适当的路线，使车辆有序地通过他们，在满足一定的约束条件下（如货物需求量、发送量、车辆容量限制，行驶里程限制等），达到一定的优化目标（如里程最短，费用最小，时间尽量少等）。它涉及了多辆交通工具的服务对象的选择和路径确定两方面问题[6]。
一个典型的VRP模型可以如下表述：
（1）基本条件 现有m辆相同的车辆停在一个共同的源点，它需给n个客户提供货物，顾客为。
（2）模型目标 确定所需的车辆数N，并指派这些车辆到一个回路中，同时包括回路内的路径安排和调度，使总费用最小。
（3）限制条件：N不大于m；每一个订单都要完成；每辆车完成任务后都要回到源点；车辆的容量限制不能超过；特殊问题还需考虑时窗限制；运输规章限制[7]。
3.2 节约算法
节约算法（Saving Algorithm）是用来解决运输车辆数目不确定的VRP问题，它是目前用来解决VRP模型最有名的启发式算法。

3.2.1节约算法的基本原理
节约算法的核心思想是将运输问题中存在的两个回路（0，… ，i，0）和（0，j，… ，0）合并成一个回路（0，… ，i，j，…，0）。在上面的合并操作中，整个运输问题的总运输距离会发生变化，如果变化后总运输距离下降，则称节约了运输距离[6]。相应的变化值，叫做节约距离，如式（1）所示。
（1）
调整过程如图3所示[8]。

j
j

i
0
0

i

调整前 调整后

图3-1 节约算法的图像描述

3.2.2节约里程算法主要步骤
已知条件:需求点集={1,2,…, n},各点需求量,各点间最短距离。
第一步,形成一个初始解。确定各车辆配送点集令, =1,2,…,n (先采取单点配送)。
第二步,进行节约度的计算。计算所有点对的节约度，然后对计算结果进行升序排列。
第三步，进行回路的合并。从升序排列的节约度序列中的最上面的值开始，直到节约里程的队列空为止,重复下列步骤:按照节约里程队列从大到小的顺序,分析客户i和j之间合并的可能性(是否满足装载限制条件、不在同一路径内以及合并次数不超过2),将i, j连接起来,即可令。如果不是这样,则从节约里程队列中去除当前的节约里程，分析下一个客户对[9]。
3.3 扫描算法
扫描算法（Sweep Algorithm）也是用于求解车辆数目不限制的VRP问题，与节约算法不同的是，它属于亚启发式算法，而节约算法属于构造算法。

3.3.1 扫描算法的基本原理
扫描算法是一种“先分组后路线”的算法。所谓分组，即指派给每辆车一组点。一种简单的分组方法是将以配送中心为原点的坐标平面划分为多个扇形区域，并初步将每个扇形区域的点分派给一辆车，然后扩充路线。如果在进行了一次“分组-路线”的路线构造后，还存在未分配点，则再进行“分组-路线”程序。如此反复，直到所有的点均已分配为止[10]。
3.3.2 扫描算法的主要步骤
（1）以起始点0点作为极坐标系的原点，并一连通图中的任意一顾客点和原点的连线定义为角度零，建立极坐标系。然后对所有的顾客所在的位置，进行极坐标变换。
（2）分组 从最小角度的顾客开始建立一个组，按逆时针方向，将顾客逐个加入到组中，直到顾客的需求总量超出了负载的限制。然后继续建立一个新的组，继续按逆时针方向，将客户加入组中。
（3）重复（2）中的过程，直到所有客户都被分类为止。
（4）路径优化 对各个组内的单回路进行路径优化[11]。
3.4改进后的最近插入法
TSP模型是单回路运输问题的最为典型的一个模型，它的全称是Traveling Salesman Problem1，中文叫做旅行商问题。它是一个典型的NP-Hard问题，对于大规模的线路优化问题，无法获得最优解。最近插入法就是一种解决此问题的启发式算法。
3.4.1 最近插入法
最近插入法是Rosenkrantz和Stearns等人在1977年提出的一种用于解决TSP(旅行商)问题的算法。最近插入法由四步完成：
（1）找到最小的节点，形成一个子回路（subtour），。
（2）在剩下的节点中，寻找一个离子回路中某一节点最近的节点。
（3)在子回路中找到一条弧（i，j）,使得+-最小，然后将节点插入到节点，之间，用两条新的弧(i，k)，（k，j）代替原来的弧（i，j），并将节点加入到子回路中。
（4）重复步骤（2）、（3），直到所有的节点都加入到子回路中。
这样，子回路就演变为了一个TSP的解[12]。
由于最近插入法解决的是单回路运输问题，故笔者在此方法基础上进行改进和修正，使其能解决多回路运输VRP问题。有改进的方法如下：
3.4.2 改进的最近插入法
（1）找到最小的节点，形成一个子回路（subtour），。
（2）在剩下的节点中，寻找一个离子回路中某一节点最近的节点。若此时回路的总货运量未超过车的载重限制，则继续步骤（3）。否则，转（1）寻找新的一条回路。
（3）)在子回路中找到一条弧（i，j）,使得+-最小，然后将节点插入到节点，之间，用两条新的弧(i，k)，（k，j）代替原来的弧（i，j），并将节点加入到子回路中。若此时该回路的总路程为未超过车辆的行程限制，则继续步骤（4）。否则转步骤（1），寻找新的一条回路。
（4）重复步骤（2）和（3），直到每一个节点都被归入某一个子回路中。

第4章 百源木业有限公司配送路线优化研究
4.1 建立VRP模型
多回路运输问题时现实生活中十分常见的一种调配问题。此类调配问题的核心问题是车辆调度。因此VRP模型也应运而生，成了解决多回路问题的一个相当成功的模型。据此对百源木业有限公司的配送系统建立VRP模型。
基本条件：百源木业公司需给9个客户送货，客户依次为1，2，…,9，现有1辆7吨（长7.8m,宽2.2m,高3.6m）的货车（每百公里油耗21L），2辆11吨(长9.5m,宽2.3m,高3.6m)的货车(每百公里油耗27L)，柴油每升7.07元，司机每天工资100元。
模型目标：确定所需要的车辆的数目N、车辆类型、司机数量以及各车行走的路径，并指派这些车辆到一个回路中，同时包括回路内的路径安排和调度，使得运输总费用最小。
限制条件：
（1）基于人性化与安全的考虑，当运输里程超过350公里时，需配备两名司机，为防止突发运输事件，车辆必须当天回到公司，减去去由于装卸货等影响因素，各车最大运输距离为600公里。
（2） 每辆车完成任务之后都要回到源点0处。
（3） 车辆的容量限制不能超过。7吨的货车最多可装300张细木工板，11吨的最多可装500张细木工板。11吨货车运输单价比7吨的低，优先使用11吨车，若不超过300张细木工板，则使用7吨货车。
4.2百源木业公司的配送线路的分析与优化
已知百源木业公司为0点，分别向9个小客户点配送细木工板，其拥有一辆7吨的车和两辆11吨的车， 7吨卡车最大容量为300张细木工板，11吨卡车最大载量为500张。设各点间的距离为，节约距离为。每辆车的载货量为，各点需求量为，每辆车的行驶里程为，且公里，婺源为0点，客户点1，2，…，9。

各县市的细木工板运量和配送距离如表2所示。
表4-1 运输任务表
客户
1景德镇
2乐平市
3鹰潭市
4贵溪市
5德兴市
6上饶市
7常山县
8开化县
9黄山市
货运量（张/周）
180
120
120
60
80
220
70
90
200
配送距离（km）
75.9
89.2
186.7
170.3
57.0
153.8
87.0
81.5
82.5

4.2.1 原配送线路基本数据分析
目前，百源木业有限公司对小客户公司采用的配送模式如图2所示。各配送线路低得里程，所需司机数量及工资的基本情况如表3所示。
表4-2 配送信息表
路线
运距
运货量
车型
司机
0-1-2-0
213.7km
300
7吨货车
1
0-3-4-0
373.4km
180
7吨货车
2
0-5-6-0
315.4km
300
7吨货车
1
0-7-8-0
202.7km
160
7吨货车
1
0-9-0
165.0km
200
7吨货车
1

由上表可知，公司每周需7吨货车5车次配送，司机6人次，所需工资600元，运输总里程为1270.2千米，消耗的柴油266.75升，所需燃油费1885.87元，一共花费2485.87元。

4.2.2 基于节约算法的企业配送路线优化
首先，确定各县市间的最短距离，县市间最距离表4所示。

表4-3 各县市间最短距离表 （单位：千米）
县市
0婺源县
1景德镇
2乐平市
3鹰潭市
4贵溪市
5德兴市
6上饶市
7常山县
8开化县
9黄山市
0婺源县
0
75.9
89.2
186.7
170.3
57.0
153.8
87.0
81.5
82.5
1景德镇

0
48.6
157.1
173.8
86.1
194.3
161.2
148.9
154.7
2乐平市

0
97.3
117.0
48.6
143.1
158.1
156.4
170.5
3鹰潭市

0
16.4
125.0
98.5
170.2
206.3
268.7
4贵溪市

0
107.2
81.5
153.9
190.1
251.3
5德兴市

0
104.6
103.2
98.3
103.1
6上饶市

0
83.3
115.7
232.0
7常山县

0
34.2
126.8
8开化县

0
91.4
9黄山市

0
数据来源：谷歌地图
然后，形成一初始解，，令，，最短路径（=1，…，9），且公里，载货量，且，对9个客户点进行标记，且。
其次，求节约里程。根据最短距离表，根据式（1）计算出用户间的节约里程,并由大到小排列，编制节约里程顺序表，如表5所示。

表4-4 节约里程顺序表 （单位：千米）

连接点
节约
里程
连接点
节约
里程
连接点
节约
里程
连接点
节约
里程
3-4
340.6
3-5
118.7
1-4
72.4
2-7
18.1
4-6
242.6
1-2
116.5
3-8
61.9
2-8
14.3
3-6
242.0
5-6
106.1
4-8
61.7
1-8
8.5
2-3
178.6
1-3
105.5
7-9
52.7
6-9
4.3
6-7
157.5
3-7
103.5
1-5
46.8
1-9
3.7
2-4
142.5
4-7
103.4
5-7
40.8
1-7
1.7
7-8
124.3
2-6
99.9
5-8
40.5
4-9
1.5
4-5
120.3
2-5
97.6
5-9
36.4
2-9
1.2
6-8
119.6
8-9
72.6
1-6
35.4
3-9
0.5

最后，按节约里程从大到小合并路径
（1）对于
。
故合并3，4两点，则。
（2）对于
。
故合并4，6两点，则
（3）对于因为3与6处在同一回路中，故不满足合并条件。
（4）对于故不满足合并条件。
（5）对于
。
故合并6，7两点，则
。
（6）余下各点的货运量均大于30，故回路0-3-4-6-7-0不能再与其他点合并。接下来的讨论将跳过与点3，4，6，7相关的。
（7）对于
。
故合并1，2两点，则。
（8）对于
。
故合并2，5两点，则
（9）对于
。
故合并8，9两点，则。
（10），故线路0-1-2-5-0与线路0-8-9-0不能合并。
至此，合并结束。
最后得到的最优结果如表6所示，优化线路图如图4所示。
表4-5节约法优化结果
路线
运距
运货量
车型
司机
0-3-4-6-7-0
454.8km
470
11吨货车
2
0-1-2-5-0
230.1km
380
11吨货车
1
0-8-9-0
255.4km
290
7吨货车
1
由上表可知，公司每周需11吨货车2车次和7吨货车1车次配送，司机4人次，所需工资400元，运输总里程为940.3千米，消耗的柴油239.56升，所需燃油费1686.60元，一共花费2086.60元。
0
1
2
3
4
5
6
8
7
9

图4-1 节约算法求解线路结果

4.2.3 基于扫描算法的企业配送路线优化
对百源木业周边的9个县市采用扫描算法进行配送线路的优化。
首先建立极坐标系：以百源木业有限公司所在地婺源县作为原点，并以点1景德镇与原点的连线为零角度建立极坐标系，各点的货运量及极坐标的角坐标值如表7所示。坐标系如图5所示。

表4-6 运量和极坐标的角坐标值
客户
1景德镇
2乐平市
3鹰潭市
4贵溪市
5德兴市
6上饶市
7常山县
8开化县
9黄山市
货运量（张/周）
180
120
120
60
80
220
70
90
200
角坐标
0
34
46
52
61
103
152
169
238
0
1
2
3
4
5
6
8
7
9

图4-2 扫描算法的扫描过程
然后分组：从角度为零向逆时针方向进行扫描，如图所示。第一个被分组的是客户1，=180；继续转动，下个被分组的是客户2，=180+120=300；继续转动，下个被分组的是客户3，300+120=420；继续转动，下个被分组的是客户4，=420+60=480；继续转动，下个被分组的是客户6，=480+80=560>500，由于超过了限制，按分组规则，需要一个新的组，这样在第一组里只有客户1，2，3，4，=480。
进行第二组扫描，最先扫描到的是客户5，=80；继续转动，下个被分组的是客户6，=80+220=300；继续转动，下个被分组的是客户7，=300+70=370；继续转动，下个被分组的是客户8，=370+90=460；继续转动，下个被分组的是客户9，=460+200=660>500，超过限制，所以需要一个新的组，这样在第二组中只有客户5，6，7，8，=460。
在第三组中只剩一个客户9，故顾客9单独在一组，=200。
这时，可以得到如图6所示的分组结果。
0
1
2
3
4
5
6
8
7
9

图4-3 扫描算法求解结果
最后对各子回路内的线路优化：对上面的3个组，都已经是一个单回路运输问题，对每个组进行线路优化。供应点0是任何一个组的TSP问题的起点和终点，用最近插入法分别对三个客户组进行求解。
对第一组进行求解。比较表4-2 中从0出发的所有路径大小，

这样，就有顾客点0，1构成一个子回路，。
然后考虑剩下顾客点2，3，4到0和1中某一点的最小距离：

由于对称性，无论将2插入到0和1之间往返路径中，结果都是一样的，这样，构成了一个新的子回路。
接下来考虑剩下的顾客点3，4到0，1，2中某一点的最小距离

顾客点3有3个位置可以插入，现在分析将点3加入到哪里合适。
（1） 插入到（0，1）之间，。
（2） 插入到（1，2）之间，。
（3） 插入到（2，0）之间，。
比较可知，插入到（2，0）之间增量最小，所以将顾客点3加入到（2，0）间，结果为
重复上面的步骤，将顾客点4加入到子回路中，就可得到一个用最近插入法求得的可行解，，总行驶距离为：。
对第二组进行求解，可得，总行驶距离为：。对第三组进行求解，可得，总行驶距离为：。
最后得到的最优结果如表8所示，优化线路图如图7所示。
表4-7扫描算法优化结果
路线
运距
运货量
车型
司机
0-1-2-3-4-0
408.5km
480
11吨货车
2
0-5-6-7-8-0
360.6km
460
11吨货车
2
0-9-0
165.0km
200
7吨货车
1
由上表可知，公司每周需11吨货车2车次和7吨货车1车次配送，司机5人次，所需工资500元，运输总里程为934.1千米，消耗的柴油242.31升，所需燃油费1713.11元，一共花费2213.11 元。
0
1
2
3
4
5
6
8
7
9

图4-4 扫描算法求解线路结果
4.2.4 基于改进的最近插入法的企业配送路线优化
令T={0},N={0，1，2……,10}，比较表4-2 中从0出发的所有路径大小。因为，所以就有顾客点0，1构成一个子回路，，此时，。
然后在剩余顾客点（1，2，3，4，6，7，8，9）中寻找到0和5中某一点的最小距离，，,因为，所以在子回路插入点1。由于对称性，无论将1插入到0和5之