城市配送中心车辆路径优化问题研究.doc

兰州交通大学毕业设计（论文）摘要车辆路径问题是运输配送中的难题之一，也是物流系统优化的关键一环。对此，国内外学者进行了广泛而深入的研究，提出了不同条件下的多种求解方法。各种方法都优点和不足之处，也有其应用上的局限和障碍，如何有效而充分地运用这些方法解决实际问题，使之服务于物流配送实践，是重要的研究课题。基于配送车辆线路问题的复杂性和多样性，相关软件的使用将是一个必然趋势。本文简要介绍了国内外车辆路径问题的发展现状，对于配送中心车辆相关概念进行了介绍。对单车辆和多车辆配送情况简要介绍，并建立数学模型，介绍了车辆路径问题的相关算法，特别对节约里程法（克拉克-怀特算法）以及Logware软件中的ROUTER模块的原理和方法深入研究，探讨了多辆车情况下的配送车辆线路问题。通过一个案例，应用节约里程法对算例进行线路安排，与Logware软件的得到的线路方案进行对比，二者结果相近，但软件的计算速度更快，效率更高。此外，分析了节约里程法和Logware软件对多车辆线路的结果。关键字：车辆路径问题；配送；节约里程法（克拉克-怀特算法）；Logware软件。兰州交通大学毕业设计（论文）AbstractThe vehicle routing problem is one of the difficult problems of transport distribution and one important part of the logistics system optimization. For this, the domestic and overseas scholars make much extensive and in-depth research, and put forward solutions under different conditions. Every method has its advantages and disadvantages, also has its limitation and obstacle on application. It is an important research subject that how to effectively make full use of these methods to solve the actual problem, and service the logistics distribution practice. Based on the complexity and diversity of the vehicle routing problem, to use of the related software will be a necessary trend. This paper briefly introduces the development status quo of vehicle routing problem at home, For distribution center vehicle related concepts are introduced .on a single vehicle and multiple vehicle distribution is briefly introduced, introduces the algorithm of vehicle routing problem, especially for saving mileage (Clark - White algorithm) and the principle and method of ROUTER module in Logware software research. discusses the distribution vehicle line car case arrangement problem. Through a case study, application of saving algorithm for line arrangement for example, compared with the circuits Logware software obtained arrangement scheme, the two results are similar, but the speed of calculation software faster, more efficient. In addition, analyses the arrangements of the vehicle line C-W algorithm and the result of Logware software.Key words: Vehicle Routing Problem, Distribution, Saving Mileage（Clarke Wright Algorithm）, Logware Software67目录摘要IAbstractII第一章 绪论1第一节 研究背景和意义1第二节 研究现状3一、国外研究现状3二、国内研究现状4第三节 研究思路5第二章基本理论概述7第一节 配送7一、配送的概念7二、配送的要素7三、配送的作用9第二节 物流及配送中心10一、物流的概念10二、配送中心的概念12三、配送中心的功能13第三节 旅行商问题15一、旅行商问题介绍15二、旅行商问题的数学模型15第三章 车辆路径问题及其相关算法18第一节 车辆路径问题18一、车辆路径问题概述18二、车辆路径问题的分类20三、车辆路径问题的构成要素23第二节 求解VRP问题的算法24一、求解VRP问题的启发式算法24二、求解VRP问题的精确算法27第四章 车辆路径问题的数学模型及求解方法34第一节 VRP的数学模型34一、物流配送中的VRP描述34二、物流配送中VRP的数学模型35第二节 节约里程算法解决VRP问题36一、节约里程算法介绍36二、节约历程算法原理37三、运算步骤38四、节约里程法优缺点39第三节 Logware软件解决VRP问题40一、Logware软件概述40二、利用ROUTER模块求解VRP问题40第五章 案例分析极其结果分析46第一节 案例46第二节 节约里程法计算47第三节 Logware 软件运行53结论59参考文献61致谢62附录63第一章 绪论第一节 研究背景和意义随着物流业向全球化、信息化及一体化发展, 配送在整个物流系统中的作用变得越来越重要。运输系统是配送系统中最重要的一个子系统, 运输费用占整体物流费用的50%左右, 所以降低物流成本首先要从降低物流配送的运输成本开始。其中, 运输线路是否合理直接影响到配送速度、成本和效益, 特别是多用户配送线路的确定是一项复杂的系统工程。选取恰当的车辆路径, 可以加快对客户需求的响应速度, 提高服务质量, 增强客户对物流环节的满意度, 降低服务商运作成本。优化运输物流, 降低运输成本, 是企业尤其是物流配送企业提高企业竞争力的有效途径之一。尽管物流活动自古有之，但直到1915年，“物流”这一名词才第一次出现在阿齐肖的市场流通中的若干问题一书中，经过数十年的理论研究和实际运作，人们认识到合理!高效的物流能够从以下几方面创造社会财富：（1）促进国民经济合理布局，有利于社会资源的优化配置；（2）有效地使用流通设施和设备，节约社会资源；（3）减少流通环节，缩短生产周期，加速资金周转；（4）简化信息流通渠道，增强社会物质财富的可调节性；（5）促进社会分工，加速生产的集中化、规模化。物流配送一般定义为：根据用户的订货要求，在物流据点进行分货、配货工作，并将配好的货物送交收货人的一种物流方式，以最终完成社会物流运送，实现资源配置的优化。配送将销售与供应结合起来，是物流系统的最后一个环节，它体现了物流效率和顾客满意程度。配送将物流和商流紧密结合，包含了商流活动，也包含了物流中若干功能要素的一种活动形式。物流中心配送是伴随着大生产、大流通而出现的一种完成资源配置和满足消费需求的方式，它实现了定时、定量、准时性、计划性、即时性，低费用甚至可以实现客户的零库存，以至可以完全取代客户原有的供应系统，用更高的供应质量和更低的供应成本，实现对用户的供应，实现企业销售和用户供应的一体化。配送作为一种专业化、社会化的服务模式，适应了经济一体化的需要，适应了社会化大生产的发展，体现了现代经济的发展趋势。在物流管理学中，研究物流配送路径优化问题并选取恰当的配送路径，可以加快对客户需求的响应速度，提高服务质量，增强客户对物流环节的满意度，降低服务商运作成本。车辆路径问题当不考虑时间要求，仅根据空间位置安排路线时称为车辆路线问题(Vehicle Routing Problem简记VRP)；当考虑时间要求安排路线时称为车辆调度问题(Vehicle Scheduling Problem简记VSP)；当同时考虑空间位置和时间要求时称为路线和调度混合问题。车辆路径问题还有确定性(Deterministic)模式和随机性(Stochastic)模式之分。确定性模式假设：其一、客户的数目在配送开始前是已知且固定的；其二、客户的需求量在配送开始前是已知且固定的；其三、两点之间的旅行时间仅取决于这两点之间的距离。而随机性模式不要求以上一个或多个假设。随机性模式又称为随机需求车辆路径问题。（1） 配送路径优化有利于提高物流经济效益。配送处于物流过程的末端，在一定程度上是物流活动的缩影。配送过程把若干物流功能结合起来，使它们有机地融为一体，从而提高了各项功能的效率；通过合理配货、共同配送，可以消除重复运输、空载运输，提高运输工具的利用率，实现合理运输，降低运输成本；通过路径的优化，可以缩短运输时间，降低运输成本，为企业提供更好的服务。（2） 路径优化是配送环节中重要的组成部分之一。配送是直接连接最终客户的物流活动。由于配送中心网络覆盖面大，信息量大而传递快，物流手段先进、设备齐全、专业化程度高，所以其服务成为现代经济中客户不可缺少的后勤。由于设备齐全、管理方式先进、有大量的信息可以提供并且可以及时传递、有网络覆盖，这些都为路径优化提供了可能性。企业可以通过计算机设备，利用所收集到的信息，提供出一个路径优化的方案，并且可以根据网络的及时信息，在具体运输时，可以做到及时更改和监督的作用。例如，可以通过网络告知司机某路段的阻塞，以便于让司机作出及时的调整。物流配送车辆优化调度，是物流系统优化中关键的一环，也是电子商务活动不可缺少的内容。对配送车辆进行优化调度，可以提高物流经济效益、实现物流科学化。可以说对物流配送车辆优化调度理论与方法进行系统研究是物流集约化发展、构建综合物流系统、建立现代调度指挥系统、发展智能交通运输系统和开展电子商务的基础。1 合理使用与调度运输工具，优化运输路线，降低企业物流成本，是物流管理的重要内容。针对物流管理中对运输车辆优化调配的要求，1959年由Dantzig和Ramser2首先提出了车辆路径问题(Vehicle Routing Problem, VRP)的数学模型。车辆路径问题已是近几十年来运筹学、应用数学、网络分析、计算机应用及交通运输等学科研究的一个热点问题，并且在通讯、生产、国防、生物、计算机应用等领域得到了广泛的应用。本文将着重研究物流配送中的车辆路径问题。VRP是一个复杂的组合优化问题，目前大都使用启发式算法求解，在可以接受的时间内获得问题的一个满意解。求解VRP的启发式算法可以分为两类，一类是经典启发式算法(19601990)，第二类是为元启发式算法(meta-heuristics)3。在算法寻优能力上，元启发式算法要优于经典启发式算法。到目前，至少有六种元启发式算法被应用到车辆路径问题中，分别为遗传算法粒子群优化算法，神经网络，蚁群算法，禁忌搜索以及模拟退火算法4。对于启发式算法,我们很难绝对地认为哪种算法更优越，其在问题求解中都有各自优缺点。物流的魅力在于其潜在着很大的利润空间，只要不断挖掘，将会产生很多意想不到的利润之源。提高物流经营水平，降低物流成本是现在物流追求的永恒主题。选址、库存与运输是决定物流管理绩效水平的三个主要驱动因素。本文以提高物流配送效率、质量为目标，对优化配送中运输调度的车辆路径问题（VRP）进行数学分析，并将改进的蚁群算法运用在路径优化策略中，研究如何建立计算机物流配送优化调度管理系统，这对于物流配送企业实现计算机配送调度，降低成本和提高物流经营管理水平将具有重要的参考价值。应该说，课题的研究具有较强的理论和实践意义。第二节 研究现状一、国外研究现状在国外，车辆优化调度研究已广泛用于生产、生活的各个方面，如报纸投递及路线的优化、牛奶配送及送达路线的优化、电话预定货物的车辆载货和线路设计、垃圾车的路线优化、连锁商店的送货及线路优化等等。目前，研究水平已有很大发展，其理论成果除在汽车运输领域外，在水运、航空、通讯、电力、工业管理、计算机应用等领域也有一定的应用，还用于轮船公司运送货物经过港口与货物安排的优化设计、交通车线路安排、生产系统中的计划与控制等多种组合优化。1962年，Balinski等人首先提出VRP的集分割，直接考虑可行解集合，在此基础上进行优化，建立了最简单的VRP模型。 1971年，Eilon提出将动态规划法用于固定车辆数的VRP，通过递归方法求解。 1974年，Wren Gillett等人提出扫描算法，将该算法应用于车辆调度问题，并和当时其它算法进行了比较，证明该算法所求得的解较优于其它方法。1981年，Christofides等人提出了k度中心树和相关算法，对固定车辆数m的m-TSP进行了进行k度中心树松弛。后来，MLFishe对这种方法做了进一步改进，可求解有134个客户的VRP。 1991年，Gendreau等人将禁忌搜索方法应用于VRP，它是比较好的启发式算法，可以成功地应用于许多经典的VRP。1996年，JLawrence将遗传算法用于VRP的研究，有效的求解出带时间窗限制的VRP。二、国内研究现状在我国，有关车辆路径问题的研究是在20世纪90年代以后才逐渐兴起的，比国外相对落后。随着顾客需求的变化，运输车辆的调度显得日益重要。近年来，我国理论界逐渐开始关注车辆路径问题的研究，并已取得初步成果。蚁群算法、启发式算法以及一些混合算法被学者们广泛的利用，代表了较近的研究思想。启发式算法作为一种逐次逼近的算法，虽然不一定得到最优解，但是可以高效率地得到具有较高精度的解，而且也易于考虑各种实际问题，因此，现已成为解决VRP问题的重要方法。与传统的启发式算法相比，近年来所采用的一些新的启发式算法，通过对启发式规则和搜索方式的改进，在求解多节点、多约束的VRP问题上可以获得较快的收敛速度和较高质量的全局解。浙江大学蔡延光等人运用模拟退火算法和遗传算法求解多重车辆调度问题，并将其集成为智能算法库，作为设计智能运输调度系统的依据。鞍山钢铁学院李大卫6和东北大学姜大力7等分别针对有时间窗和无时间窗约束下的车辆路径问题用基因编码遗传算法求解，结果在较快速度下得到了近优解。崔雪丽、马良和范炳全8等人基于近年来出现的新型智能优化思想：人工蚂蚁系统，给出了一种可快速求解VRP的蚂蚁搜索算法。通过定义基本的人工蚂蚁状态转移概率，并结合局部搜索策略，用迭代次数控制算法的运行时间，从而使该方法具有使用意义和可操作性。经一系列数据测试和验证，与若干已有的经典算法相比较，获得了较好的结果。杨善林人等提出一种基于蚁群优化的混合算法来解决VRP。首先提出一种ACO 算子，然后加入局部搜索机制并使用基于问题的特定启发信息节约量来改进算法。尹小峰等针对了蚁群算法存在的过早收敛问题，引入节省量以及车辆载重利用率两种启发式信息对蚁群算法加以改进，并加入2opt方法对问题求解进行局部优化，计算机仿真结果表明，这种混合蚁群算法对求解车辆路径问题有较好的改进效果。由于物流对于中国来说，还算是一个新兴行业，所以在中国物流的发展当中，可以借鉴一下国外的发展经验。物流的发展，尤其是配送路线优化的发展，在中国存在着以下几点的困难：（1） 要进行配送路线的优化，先进设备的使用存在着一定的困难。因为物流的现代化，需要一系列配套设备的使用，投资比较大，成本回收慢。例如一家物流企业使用了先进的设备，但是与其往来的企业无法提供相应先进的设备和该企业配合，那么设备的利用率以及优势是无法体现出来的，现代化是无法展开的。（2） 在中国社会中，对于物流行业的偏见，配送路线优化工作的展开有一定的困难。很多人并不了解物流，认为物流只是简单的运输，不愿意进行投资发展，忽略了其中的价值，这造成了物流发展的阻碍。（3） 专业型人才短缺，使得没有专业型人才进行配送路线优化工作。先进的设备以及现代化管理，都需要物流专业型人才的加入，而在中国很多物流企业中，缺少这种物流专业型人才。（4） 物流专业型软件没有得到广泛应用，使得配送路线优化存在着困难。第一，很多物流企业只是靠经验来判断路线，并没有真正得到优化，没有使用计算机以及与其配套的专业型软件，软件的使用可以使路线的选择更加优化，也可以减少劳力。第二，对于物流专业型软件以及系统的开发，没有得到重视。在中国，软件在物流中的应用，越来越广泛，并且带给企业以及社会很大的经济效益，帮助企业解决了很多困难。物流中的软件，正朝着定制化，通用化，行业化的方向前进发展着。第三节 研究思路本文是研究配送中心车辆路径问题的。Logware是物流专用软件，可以通过软件来安排车辆的路线，优化配送过程，提高效率，增加经济效益。本文的研究思路如下：第一章，讲述研究意义、以及配送车辆路线的研究现状、发展现状和总体思路等问题。第二章，介绍物流配送车辆路线的相关概念。首先，了解配送中心的相关概念。其次，掌握配送的概念及方法。最后，对单车辆路径问题(旅行商问题)进行了介绍。第三章，对车辆路径问题进行研究。对车辆路径问题进行综合性了解，对车辆路径问题的相关知识进行了比较详细的描述。在整个过程中，解决了车辆路径问题的相关概念、分类及其构成要素。在分析完成后，描述了车辆路径问题的相关算法。必须要清楚车辆路线研究的必要性以及重要性，这样才能有的放矢，抓住关键的地方进行研究。而且车辆路线安排的方法有很多，每种方法都有自己的优缺点，简要的介绍一下，比较常用的方法。第四章，车辆路径问题的数学模型及求解方法，这也是本文的主体部分。建立车辆路径问题的数学模型，并介绍了相关求解方法。首先对节约里程法进行了详细的叙述，有了较明确的节约里程法的计算步骤。接着对Logware软件及其中的ROUTER模块进行了介绍，通过Logware软件进行配送车辆路线的安排。在整个过程中，找到软件的优势以及不足之处。在这部分开始之前，应当对Logware软件进行学习，寻找实例，分析实例中各种限制条件，因为现实因素有很多，不能各个因素全部考虑到问题中去，所以要尽可能考虑周全，再在这些因素中，找到主要因素，进行分析。在分析完成后，将学习到的软件知识运用到实例当中，解决问题。第五章，案例及结果分析，运用节约里程法和Logware软件计算案例结果，并对结果进行分析，找出更符合实际的方案。找出节约里程法和Logware软件在解决车辆路线问题的优缺点，以及对于实际问题是否能完全反应，如果不能完全反应，各自忽略了哪些实际因素，而这些因素对于车辆路线有着怎样的影响。最后，对于这个文章进行概括性的总结，说明车辆路线安排的必要性，对节约里程法和Logware软件的优缺点进行了阐述。现实中和理论存在着什么样的差距，以及需要改进的地方。今后物流的发展中，企业应当重视软件的使用，使得工作流程可以更加优化。第二章 基本理论概述第一节 配送配送是现代物流的一个重要内容。是指在经济合理区域范围内，根据客户要求，对物品进行拣选、加工、包装、分割、组配等作业，并按时送达指定地点的物流活动。 配送是物流中一种特殊的、综合的活动形式，是商流与物流紧密结合，包含了商流活动和物流活动，也包含了物流中若干功能要素的一种形式。一、配送的概念总的来说，配送是物流活动中一种非单一的业务形式，它与商流、物流、资金流紧密结合，并且主要包括了商流活动、物流活动和资金流活动，可以说他是包括了物流活动中大多数必要因素的一种业务形式。从物流来讲，配送几乎包括了所有的物流功能要素，是物流的一个缩影或在某小范围中物流全部活动的体现。一般的配送集装卸、包装、保管、运输于一身，通过这一系列活动完成。将货物送达的目的。特殊的配送则还要以加工活动为支撑，所以包括的方面更广。但是，配送的主体活动与一般物流却有不同，一般物流是运输及保管，而配送则是运输及分拣配货，分拣配货是配送的独特要求，也是配送中有特点的活动，以送货为目的的运输则是最后实现配送的主要手段，从这一主要手段出发，常常将配送简化地看成运输中之一种。从商流来讲，配送和物流不同之处在于，物流是商物分离的产物而配送则是商物合一的产物，配送本身就是一种商业形式。虽然配送具体实施时，也有以商物分离形式实现的，但从配送的发展趋势看，商流与物流越来越紧密的结合，是配送成功的重要保障。日本工业标准（JIS）将配送定义为“把货物从物流据点送到交货人处”，是“从配送中心到顾客之间物品的空间移动”。用最通俗的话说就是既配又送，即按用户的订货要求，在物流结点进行分货、配货工作并将配好的货物送交收货人。“配”包括货物的分拣和配货活动；“送”则包括各种送货方式和送货行为。我国发布的国家标准“物流术语”中关于配送的解释为；在经济合理区域范围内，根据用户的要求，对物品进行拣选、加工、包装、分割、组配等作业，并按时送达指定地点的物流活动。二、配送的要素（一）集货集货，即将分散的或小批量的物品集中起来，以便进行运输，配送的作业。集货是配送的重要环节，为了满足特定客户的配送要求，有时需要把从几家甚至数十家供应商处预订的物品集中，并将要求的物品分配到指定容器和场所。集货是配送的准备工作台或基础工作，配送的优势之一，就是可以集中客户的进行一定规模的集货。（二）分拣分拣是将物品按品种、出入库先后顺序进行分门别类堆放的作业。分拣是配送不同于其他物流形式的功能要素，也是配送成败的一项重要支持性工作。它是完善送货、支持送货准备性工作，是不同配送企业在送货时进行竞争和提高自身经济效益的必然延伸。所以，也可以说分拣是送货向高级形式发展的必然要求。有了分拣，就会大大提高送货服务水平。（三）配货配货是使用各种拣选取设备和传输装置，将存放的物品，按客户要求分拣出来，配备齐全，送入指定发货地点。（四）配装在单个客户配送数量不能达到车辆的有效运载负荷时，就存在如何集中不同客户的配送货物，进行搭配装载以充分利用运能、运力的问题，这就需要配装。跟一般送货不同这处在于，通过配装送货可以大大提高送货水平及降低送货成本，所以配装也是配送系统中有现代特点的功能要素，也是现代配送不同于以往送货的重要区别之一。（五）配送运输运输中的末端运输、支线运输和一般运输形态的主要区别在于；配送运输是较短距离、较小规模、额度较高的运输形式，一般使用汽车做运输工具。与干线运输的另一个区别是，配送运输的路线选择问题是一般干线运输所没有的，干线运输的干线是唯一的运输线，而配送运输由于配送客户多，一般城市交通路线又较复杂，如何组合成最佳路线，如何使配装和路线有效搭配等，是配送运输的特点，也是难度较大的工作。（六）送达服务将配好的货运输到客户还不算配送工作的结束，这是因为送达货和客户接货往往还会出现不协调，使配送前功尽弃。因此，要圆满地实现运到之货的移交，并有效地、方便地处理相关手续并完成结算，还应讲究卸货地点、卸货方式等。送达服务也是配送独具的特殊性。（七）配送加工配送加工是按照配送客户的要求所进行的流通加工。在配送中，配送加工这一功能要素不具有普遍性，但往往是有重要作用的功能要素。这是因为通过配送加工，可以大大提高客户的满意程度。配送加工是流通加工的一种，但配送加工有它不同于流通加工的特点，即配送加工一般只取决于客户要求，其加工的目的较为单一。三、配送的作用配送将销售与供应结合起来，是物流系统的最后一个环节，它体现了物流效率和顾客满意程度。配送将物流和商流紧密结合，包含了商流活动，也包含了物流中若干功能要素的一种活动形式。配送主要涉及从供应链的制造商到终端客户的运输和储存活动。运输的功能在于完成产品空间上的物理转移，克服制造商与客户之间的空间距离，从而产生空间效用；而储存的功能就是将产品保存起来，客户产品供应与需求在时间上的差距，创造时间效用。所以配送创造了时间效用和空间效用。根据物流的定义和系统的概念，物流体系是为完成物品实体从供应地到接收地的流动而将运输、仓储、装卸搬运、流通加工包装和物流信息等融为一体，构成了物流体系的功能体系。配送的作用表现在:（一）企业采用配送体制分销领域采用配送体制，可以降低物流成本，提高服务水平，从而可以扩大销售、扩大市场、增强企业竞争能力。产品实行配送体制，配送需要多少，就生产多少，可以实现产品零库存，可以获得最大的节约和最大的效益。采购领域实行配送体制，就可以实现企业需要多少，供应商就配送多少，什么时候需要，供应商就什么时候送货。因此企业不需要设置原材料库存，流通企业也不需要设置流通库存，都可以做到零库存经营，大大降低经营成本。企业零库存经营，节省下来的大量储备资金，可以改善企业的财务状况，增强企业经济实力，促进企业发展。企业实行配送体制，导致生产体制、分销体制以及采购体制相应的革命性的变化，促进企业经营管理水平的提高。(二)对于广大用户来说，提高了物流服务水平。配送能够按时按量、品种配套齐全地送货上门，一方面使用户免除了出差采购运输进货等劳役之苦，简化了手续，方便了用户，节省了成本，提高了效率;另一方面保障了物资供应，保障了企业生产和流通的正常进行，满足了人们生产生活的物资需要和服务享受。(三)配送提高了物资利用率和库存周转率。配送采用配送中心集中库存，可以利用有限仓库，使有限库存为更大范围更多客户所利用，需求更大、市场面广，物资利用率和库存周转率必然大大提高。还可以使仓储与配送环节建立和运用规模经济优势，使单位存货量和管理的总成本下降。(四)配送完善了干线运输中心的社会物流功能体系。采用配送作业方式，可以在一定范围内，将干线、支线运输与仓储等环节统一起来，使干线输送过程及功能体系得以优化和完善，形成一个大范围物流与局部范围配送相结合的、完善的物流配送体系。(五)配送对于整个社会和生态环境来说，也起着重要的作用。配送可以节省运输车辆，缓解交通紧张状况，减少噪声、尾气排放等运输污染，为保护生态平衡、创造美好家园作出贡献。(六)发展配送有利于提升和优化物流结构和产业结构，使运输业、仓输业获得增长的机会;同时与其相关的电信服务、代理业和客户服务等行业的发展将成为第三产业的新增长点。我国从历史上曾采用的一般送货，发展到以高科技做支撑，再成为企业发展战略手段的配送，是最近一二十年的事情，20世纪90年代以来的实践证明，配送是一种非常好的物流方式，它彻底改变了传统的流通模式和方式，为用户提供了更加方便、快捷的服务，提高了流通企业的效率。但进展缓慢、设备落后、信息化程度低也是目前的一个基本状况，所以，借鉴发达国家的先进经验，结合我国具体实际，发展符合我国国情的配送体系，使物流配送向正规化、规模化发展显得十分重要。第二节 物流及配送中心一、物流的概念研究物流的定义，有助于我们从历史的角度深刻认识物流的本质，通过比较不同的物流定义可加深对物流概念的理解。本文列出了美国、欧洲、日本以及中国的物流定义。（一）美国的物流定义可以将美国的物流定义归纳为四大派别：管理派、工程派、军事派、企业派。（1）管理派管理派以物流管理协会为代表，1985年该协会对物流做了这样的定义：物流是对货物、服务及相关信息从起源地到消费地的有效率、有效益的流动和储存进行计划、执行和控制，以满足顾客要求的过程。（2）工程派工程派以美国物流工程师学会为代表，1974年该学会对物流所做的定义为：物流是与需求、设计、资源供给与维护有关，以支持目标!计划及运作的科学、管理工程及技术活动的艺术。（3）军事派美国空军1981年关于物流的定义对具有代表性，其定义是：物流是计划!执行军队的调动与维护的科学。按照最全面的定义，物流与军事活动的诸方面相关：a.军事物资的设计、开发、采购、储存、运输、分配、保养、疏散及废弃处理；b.军事人员的运输、疏散和安置；c.军事装备的采购或建设、保养、运营及废弃处理；军事服务的采购或提供。（4）企业派美国一家著名物流公司Exel logistics Co1997年在物流术语词汇集中给物流下了三种定义：物流是与计划和执行供应链中商品及物料的搬运、储存及运输相关的所有活动，包括废弃物品及旧品的回收复用；物流是围绕物料管理和实物流通所发挥的功能；物流是对静态和动态库存的管理。（二）欧洲的物流定义欧洲物流协会1994年发表的物流术语中将物流定义为：物流是一个系统内对人员及、或商品的运输、安排及与此相关的支持活动的计划、执行与控制，以达到特定的目的。日本日通综合研究所1981年在物流手册上对物流的定义是：物流是物质资料从供给这项需要者的物理性移动，是创造时间性、场所性价值的经济活动。从物流的范畴来看，包括：包装、装卸、保管、库存管理、流通加工、运输、配送等诸种活动。如果不经过这些过程，物就不能移动。中华人民共和国标准 物流术语1997年将物流定义为：物品从供应地向接受地的实体流动中，根据实际需要，将运输、储存、装卸、搬运、包装、流通加工、配送、信息处理等功能有机结合来实现用户要求的过程9。目前国际上物流学界对于物流产生的原因基本上有两种观点：一种是经济动因，他们认为物流概念是起源于人们对协调经济活动中物流及其相关活动的追求；另一种军事动因，物流概念已经在1905年由美国少校琼西贝克(Major Chauncey BBaker)明确地解释了,即那个与军备的移动!与供应相关的战争的艺术的分支13。二、配送中心的概念配送中心常用名称，有多意思，配送中心是接受并处理末端用户的订货信息，对上游运来的多品种货物进行分拣，根据用户订货要求进行拣选、加工、组配等作业，并进行送货的设施和机构。是从供应者手中接受多种大量的货物，进行倒装、分类、保管、流通加工和情报处理等作业，然后按照众多需要者的订货要求备齐货物，以令人满意的服务水平进行配送的设施。（一）标准的定义“接受并处理末端用户的订货信息，对上游运来的多品种货物进行分拣，根据用户订货要求进行拣选、加工、组配等作业，并进行送货的设施和机构。”物流企业操作指南在对此进行科学完善的基础上，权威性的指出了配送中心的设计、流程、模式等等。（二）物流手册对配送中心的定义“配送中心是从供应者手中接受多种大量的货物，进行倒装、分类、保管、流通加工和情报处理等作业，然后按照众多需要者的订货要求备齐货物，以令人满意的服务水平进行配送的设施。”图2.1 配送流程图（三）现代物流学的定义“配送中心是从事货物配备(集货、加工、分货、拣选、配货)和组织对用户的送货，以高水平实现销售或供应的现代流通设施。”（四）日本市场用语词典对配送中心的解释“是一种物流结点，它不以贮藏仓库的这种单一的形式出现，而是发挥配送职能的流通仓库，也称作基地、据点或流通中心。配送中心的目的是降低运输成本、减少销售机会的损失，为此建立设施、设备并开展经营、管理工作”。（五）货运物流实用手册对配送中心的解释配送中心（DC，Distribution Center)是实现配送业务的现代化流通设施。配送中的“货物配备”是配送中心主要的业务，是全部由它完成的；而送货既可以完全由它承担，也可以利用社会货运企业来完成。中华人民共和国国家标准物流术语中规定，从事配送业务的物流场所和组织，应复合下列条件：1.主要为特定的用户服务；2.配送功能健全；3.完善的信息网络；4.辐射范围小；5.多品种，小批量；6.以配送为主，储存为辅。三、配送中心的功能（一）采购功能配送中心必须首先采购所要供应配送的商品，才能及时准确无误地是为其用户即生产企业或商业企业供应物资。配送中心应根据市场的供求变化情况，制定并及时调整统一的、周全的采购计划，并由专门的人员与部门组织实施。（二）存储保管功能储存，一是为了解决季节性货物生产计划与销售季节性的时间差问题。二是为了解决生产与消费之间的平衡问题，为保证正常配送的需要，满足用户的随机需求，在配送中心不仅应保持一定量的商品储备，而且要储存商品保管保养工作，以保证储备商品的数量，确保质量完好。配送中心的服务对象是为数众多的生产企业和商业网点（比如连锁店和超级市场），配送中心需要按照用户的要求及时将各种配装好的货物送交到用户手中，满足生产和消费需要。为了顺利有序地完成向用户配送商品的任务，而且为了能够更好地发挥保障生产和消费需要的作用，配送中心通常要兴建现代化的仓库并配备一定数量的仓储设备，存储一定数量的商品。某些区域性的大型配送中心和开展“代理交货”配送业务的配送中心，不但要在配送货物的过程中存储货物，而且它所存储的货物数量更大，品种更多。由于配送中心所拥有的存储货物的能力使得存储功能成为配送中心中仅次于组配功能、和分送功能的一个重要功能之一。（三）配组功能由于每个用户企业对商品的品种、规格、型号、数量、质量送达时间和地点等的要求不同，配送中心就必须按用户的要求对商品进行分拣和配组。配送中心的这一功能是其与传统的仓储企业的明显区别之一。这也是配送中心的最重要的特征之一，可以说，没有配组功能，就无所谓配送中心。（四）分拣功能作为物流节点的配送中心，其为数众多的客户中，彼此差别很大。不仅各自的性质不同，而且经营规模也相差径庭。因此，在订货或进货时，不同的用户对于货物的种类、规格、数量会提出不同的要求。针对这种情况，为了有效地进行配送，即为了同时向不同的用户配送多种货物，配送中心必须采取适当的方式对组织来的货物进行拣选，并且在此基础上，按照配送计划分装和配装货物。这样，在商品流通实践中，配送中心就又增加了分拣货物的功能，发挥分拣中心的作用。（五）分装功能从配送中心的角度来看，它往往希望采用大批量的进货来降低进货价格和进货费用；但是用户企业为了降低库存、加快资金周转、减少资金占用，则往往要采用小批量进货的方法。为了满足用户的要求，即用户的小批量、多批次进货，配送中心就必须进行分装。（六）集散功能货物由几个公司集中到配送中心里，再进行发运、或向几个公司发运。凭借其特殊的地位以及拥有的各种先进的设施和设备，配送中心能够将分散在各个生产企业的产品集中到一起,然后经过分拣、配装向多家用户发运。集散功能也可以将其它公司的货物放入该配送中心来处理、发运，以提高卡车的满载率，降低费用成本。（七）流通加工功能配送过程中，为解决生产中大批量，少规格和消费中的小批量，多样化要求的矛盾，按照用户对货物的不同要求对商品进行分装、配装等加工活动，这也是配送中心功能之一。（八）送货功能将配好的货物按到达地点或到达路线进行送货。运输车辆可以租用社会运输力量或自己的专业运输车队。（九）传递功能它为管理者提出更加准确、及时的配送信息，也是用户与配送中心联系的渠道。（十）衔接功能在生产过程中，不但是半成品还有原材料等需要从各地运来，需要仓库储存，并对生产过程中的各道工序的物资进行配送。（十一）服务功能以顾客需要为导向，为满足顾客需要而开展配送服务。此外，配送中心还有如加工功能、运输功能、信息功能、管理功能等功能。每个配送中心一般都具有这些功能，根据对其中某一功能的重视程度不同，决定着该配送中心的性质，而且它的选址、房室构造、规模和设施等也随之变化第三节 旅行商问题一、旅行商问题介绍旅行商问题（Traveling Salesman Problem，简称TSP）是运筹学、图论以及组合优化中的著名难题，由于其有广泛的应用背景，引起了人们的极大的兴趣。TSP本身可以直接用于解决类似TSP的最优巡回线路等问题，其它例如交通车辆的巡回线路问题、民航机组人员的轮班安排问题、教师任课班级负荷分配问题、装配线进度问题、数控机床的运行问题以及生产系统传送带顺序问题等，都可以直接或间接引用TSP的求解方法加以解决。TSP一般描述为：旅行商从起始点出发，经所要去的城市（节点）至少一次后返回原地，应如何安排其旅行线路，才能使总的旅行距离（或时间、费用等）最少。对于现实问题，由于限制条件的增加，TSP可以衍生出许许多多的相关问题。二、旅行商问题的数学模型一般TSP指一个旅行商访问所有城市（节点）。这里设城市0为旅行商出发城市，需要访问的l个城市编号为：1，2，l，为了便于说明问题，把旅行商问题构造成网络图，以G V，A，C 表示，其中V=0,1，1 点集，表示旅行商需要经过的地点；A=（i，j）|i，j=0,1，1，ij 弧集，表示旅行商可能走过的线路段集合；费用矩阵，表示旅行商经过对应弧段(i，j)所花的费用，如时间、距离、花费等。求解TSP即要求在加权图G中找到总费用最小的哈密尔顿（Hamilton）回路，这里点0称为源点。定义变量如下： 若弧（i，j）在线路下； 否则。则得到以下模型：其中，cij=M (1,2，1)；S为支路消去约束（subtourbreaking约束），即消去构成不完整的解，如图2.2所示，两条支路均满足分配约束，但没有构成一条完整的路线，因此不是VSP问题的解。 （2.1）图2.2 支路示意图S一般有下面几种表示法：（1） （2.2）该式说明点的某一子集必须同解中其它集相连。图2.2中， ， ，则可消去两条支路。（2） （2.3）该式暗示了任一子集R上的弧都不产生循环，因为点集R上的循环至少含有条弧。图2.2，中，则排除了产生循环的支路4564。（3） （2.4）式中一般可令那么在一条线路中，若存在弧（i，j），即xij=1，则有 （2.5）如果没有弧（i，j），即xij=0，那么有 （2.6）如图2.2中，约束加到弧45，56，64上，有合并后有 ，该式显然不成立，说明加上约束后不会产生支第三章 车辆路径问题及其相关算法第一节 车辆路径问题一、车辆路径问题概述车辆路径问题一般定义为：对一系列发货点或收货点，组织适当的行车路线，使车辆有序地通过它们，在满足一定的约束条件（如货物需求量、发送量、交发货时间、车辆容量限制、行驶里程限制、时间限制等）下，达到一定的目标（如路程最短、费用最小、时间尽量少、使用车辆尽量少等）。在物流配送运输中，由于货运点多、客户多、货物种类繁多、城市交通路线复杂、运输服务地区内运输网点分布不均匀等诸多因素的影响，同时还要满足客户提出的如时间窗等约束条件的要求，使得如何安排最佳路线，如何使配装和配送路线有效搭配等，成为物流配送中的难点。 合理解决车辆路径问题，不仅可以简化配送程序、减少配送次数、降低配送车辆的空载率，从而降低物流成本，提高经济效益，而且可加快对客户需求的响应速度，提高服务质量，增强客户对物流环节的满意度等。因此，车辆路径问题是物流配送过程中的关键问题，是运筹学与组合优化领域的热点问题，在现代物流中居于中心地位。 图3.1 车辆路径问题示意图该问题的一般描述是：已知配送中心和一系列的客户需求点的位置以及客户需求量，配送中心的车辆数量以及车型，要求合理地设计配送车辆行驶路线，在满足一定的约束条件下，使车辆从配送中心出发，每辆车完成若干需求点的配送任务后，最后返回配送中心。通过优化车辆调度，使得在满足客户需求的前提下，达到一定的目标（如行驶总旅程最短，配送成本最低，物流配送服务水平最优，配送车辆数量尽量少等）。图3.1是3条车辆行驶路线的巡回配送图，椭圆表示中心站点，箭头表示路线，圆圈表示顾客需求点。在实际的应用中，车辆路径问题受到很多条件的限制，如：（1）车辆容量限制，每辆车所服务的客户总的需求量不得大于车辆的最大载质量；（2）时间窗限制，每个客户必须在一定的时间范围内进行服务；（3）物流企业可能有多个配送中心对客户进行服务； （4）客户可能向配送中心返回一些货物； （5）客户可以被不同的车辆服务； （6）客户数量，需求量，行使路线等随机出现； （7）客户之间服务的次序存在着限制等。 在研究工作中，常针对约束条件做出一些基本假设，如：由一个配送中心，单一车型完成配送任务；被配送的是可混装的货物；各个客户的位置以及它们到配送中心的距离已知；配送中心有足够的货物以供配送，并且有足够的