同济大学交通运输工程学院硕士学位论文快递企业多点配送线网模型优化相关理论与方法的研究姓名：李炳会申请学位级别：硕士专业：交通运输规划与管理指导教师：孙焰20080101摘要摘要- 配送是快递企煦业务中直接与顾客相连麓环节。在快递公司运作的各项成本中，羁己送成本占了相当高的比例。配送线路安排的合理与否对配送速度、成本、效益影响很大，特别是多用户配送线路的确定更为复杂。采用科学、合理的方法来进行配送线网优化，是配送过程中常重要的一项工作。多点配送线网优化闻题有很高的计算复杂性，属于N P 难题，高效精确的算法存在的可能性不大。本文研究了多点配送线网模型优化的问题及其方法，将蚁群算法改进并成功运用于解决配送过程中的线网优化问题，提出了基于蚁群算法的物流配送路径优化算法。首先介绍了多点配送线霹优化闻题的相关知识，通过对研究现状的分析讨论，引出本文的研究目的和工作重点；接下来对快递企业的配送问题进行了描述，分析了配送线网优化问题的评估标准，建立了带约束条件的配送线网优化闻题的数学模型；根据该模型的具体要求，弓| 入蚁群算法，详细描述了蚁群算法在配送线网优化问题中的实现方案，分析讨论了蚁群算法的优缺点，并将蚁群算法运用到配送线网优化问题中，实现了多次配送、多种车型情况下的快递企业多点配送线飕优化算法模型。露时，针对蚁群算法的缺陷，本文提出了对该算法的几颈改进，包括：在蚁群算法中引入遗传操作、修改信息素更新策略等。最后将改进后的蚁群算法运用于线网优化问题。经过多次实验和计算，证明了用改进的蚁群算法优化配送线路，可以有效地求褥问题的最优解或近似最优解。关键字：快递，多点配送，线网优化，蚁群算法，遗传算法A b s t r a c tA B S T R A C TD i s t r i b u t i o n ，w h i c hh o l d sc o n s i d e r a b l ep r o p o r t i o na m o n gv a r i a b l ec o s t s ，i sas e c t i o nl i n k i n gw i lc o n s u m e r sd i r e c t l yi nE x p r e s sD e l i v e r ye n t e r p r i s e so p e r a t i o n T h ep l a n n i n go fv e h i c l er o u t i n gi nd i s t r i b u t i o nw i l lt a k eg r e a te f f e c to nt h ee f f i c i e n c y , c o s ta n db e n e f i t ，e s p e c i a l l yi nd i s t r i b u t i n gf o rm u l t i c o n s u m e r As c i e n t i f i ca n dr e a s o n a b l em e t h o dt ov e h i c l es c h e d u l i n gi sa ni m p o r t a n to p e r a t i o ni nE x p r e s sd e l i v e r yd i s t r i b u t i o n E x p r e s sd e l i v e r yd i s t r i b u t i o nr o u t i n go p t i m i z a t i o ni saN P - h a r dp r o b l e m H i g he f f e c t i v ee x a c ta l g o r i t h mi si m p o s s i b l et ob ea c h i e v e d T h i sp a p e rs t u d i e so nt h eo p t i m i z a t i o no fE x p r e s sd e l i v e r yd i s t r i b u t i o nr o u t i n gp r o b l e ma n ds o l v e st h ep r o b l e mu s i n gi m p r o v e da n tc o l o n ya l g o r i t h ms u c c e s s i v e l y F i r s t l y , i td i s c u s s e st h eb a s i cp r o b l e ma b o u tE x p r e s sd e l i v e r yd i s t r i b u t i o na n dt h er e l a t i v er e s e a r c hw o r k sb e f o r e ；t h e ni td e s c r i b e st h eE x p r e s sd e l i v e r yd i s t r i b u t i o np r o b l e mi nm a t h e m a t i cw a y , a n a l y z e st h ee v a l u a t i o ns t a n d a r da b o u tt h eo p t i m i z a t i o n , a n db u i l d st h e m a t h e m a t i cm o d e l ；a c c o r d i n gt ot h eb a s i cd e m a n do ft h em o d e l ，i ti n t r o d u c e st h ea n tc o l o n ya l g o r i t h m ( A C A ) ，a n daf l o wc h a r to fs o l v i n gE x p r e s sd e l i v e r yd i s t r i b u t i o np r o b l e mw i t hA C Ai sg i v e n ，t h ea d v a n t a g e sa n dd i s a d v a n t a g e so fA C Aa r ed i s c u s s e da sw e l l 。A tt h es a m et i m e ，a i m i n ga ti m p r o v i n gt h eA C A ，G e n e t i ca l g o r i t h m ( G A ) g i v e si t sa d v a n t a g e s T h er e s u l to fe x p e r i m e n t sd e m o n s t r a t e st h a tt h eo p t i m a lo rn e a r l yo p t i m a ls o l u t i o n sf o rE x p r e s sD e l i v e r yd i s t r i b u t i o nr o u t i n gp r o b l e mc a nb ee a s i l yo b t a i n e db yt h ei m p r o v e da n tc o l o n ya l g o r i t h m K e yW o r d s ：E x p r e s sD e l i v e r y , M u l t i C o n s u m e rD i s t r i b u t i o n , R o u t i n gO p t i m i z a t i o n ,A n tC o l o n yA l g o r i t h m ( A C A ) ，G e n e t i ca l g o r i t h m ( G A )珏学位论文版权使用授权书本人完全了解同济大学关于收集、保存、使用学位论文的规定，同意如下各项内容：按照学校要求提交学位论文的印刷本和电子版本；学校有权保存学位论文的印刷本和电子版，并采用影印、缩印、扫描、数字化或其它手段保存论文；学校有权提供目录检索以及提供本学位论文全文或者部分的阅览服务；学校有权按有关规定向国家有关部门或者机构送交论文的复印件和电子版；在不以赢利为目的的前提下，学校可以适当复制论文的部分或全部内容用于学术活动。学位论文作者签名：年月日同济大学学位论文原创性声明本人郑重声明：所呈交的学位论文，是本人在导师指导下，进行研究工作所取得的成果。除文中已经注明弓| 用的内容努，本学位论文的研究成果不包含任何他人创作的、已公开发表或者没有公开发表的作品的内容。对本论文所涉及的研究工作做出贡献的其他个人和集体，均已在文中以明确方式标明。本学位论文原创性声明的法律责任由本人承担。学位论文作者签名：年月日第一章绪论第一章绪论本章主要介绍了快递来多点配送线网优化问题的相关概念及研究背景，因内外此问题上的研究现状。根据研究背景提崮了本文的主要研究内容并在本章的最后简要介绍了本文的章节组织。1 。 快递业多点配送线网优化问题概述1 1 1 基本概念及相关问题市场经济的繁荣，推动了快递业的迅猛发展。快递是指快递企业收取寄件入托运的快件后，按照寄件人要求的时间，以最快的速度将其运到另一地点，递交指定的收件人；掌握运输、派送过程的全部情况并能向有关人员提供即时信息查询的门到门服务。快递对象包括函件快递和包裹快递，前者以处理文l 孛、资料、图纸、贸易单证为主，后者以处理样品、高附加值物品、社会活动礼品和家庭高档商品为主。配送是指按客户的订赞要求，在配送中心进行分货、配货，并将配好的货物及时送交客户的活动。在配送业务中，存在许多优化决策问题，本文讨论配送线鼹的优化，霹通过制定合理的配送线瓣，迅速而经济地将货物送到客户手中。优化配送线网问题类似“旅行商“ ( T S P ) l h - J 题，要求遍历所有的客户点，不同的是，配送问题是由多辆车对客户点进行遍历，每辆车负责配送的客户点以及配送线网都是不确定的，这正是配送线网优化所要解决的问题。优化配送线圈是一个N P 难问题，只有当客户和路段较少时，才能求得精确解；启发式算法成了求解该问题的一个重要方向，且出现了多种算法，如C l a r k e 和W r i g h t 提出的节约法，G i l l e t 和M i l l e r 提出的扫描法等，为求解配送线网的优化提供了有益的参考，但也存在一些| 巍题，如：节约法的组合点零乱和边缘点难以组合，扫描法为非渐进优化等。 。1 。2 优化配送的意义从应用方面看，快递企业配送线网优化，是优化配送中关键的一环，也是电子商务活动不可缺少的内容。对货运车辆进行线网优化，可以提高快递企业经济效益、实现配送科学化。对配送车辆线网优化理论与方法进行系统研究是快递企业集约化发展、建立现代调度指挥系统、发展智能交通运输系统和开展电子商务第一章绪论的基础。优化配送线网问题是N P 完备问题，般无法给出最优解，研究者们努力的躁标就是尽量逼近最优解。因此优化配送线网闻题是一个十分有应用价值的问题。从理论研究方面看，本文主要用到的蚁群算法从提出至今只有十几年，还停留在仿真阶段，尚未能提出数学解释，不过虽然研究时间不长，但己显示出在求解复杂优化问题方面的优势，其应雳前景非常广阔。可以看出，蚁群算法是一个处于发展阶段，并有广阔的发展空间和巨大的发展潜力的算法，只要投入足够的精力，就可能在理论上有所突破，这就体现出其巨大的理论研究价值。本文还运用遗传算法对蚁群舞法进行改进，遗传算法是较为成熟的优纯算法，被广泛地运用于解决实际组合优化问题。本文将遗传算法和蚁群算法相结合，对组合优化问题的研究是一种新的尝试