配送路线优化

1

带时间窗的易腐食品配送路径选择问题

目 录

摘要………………………………………………………………………………………………………………2 Abstract…………………………………………………………………………………………………………2 1 引言……………………………………………………………………………………………………………3

1.1研究背景………………………………………………………………………………………………3 1.2研究意义………………………………………………………………………………………………3 1.3研究方法………………………………………………………………………………………………4 2 理论基础………………………………………………………………………………………………………4

2.1易腐食品概述…………………………………………………………………………………………4

2.1.1易腐食品的定义………………………………………………………………………………4 2.1.2易腐食品配送特点……………………………………………………………………………5 2.1.3易腐食品的配送条件…………………………………………………………………………6 2.2时间窗概念……………………………………………………………………………………………7

2.2.1硬时间窗………………………………………………………………………………………7 2.2.2软时间窗………………………………………………………………………………………7

3 现状分析………………………………………………………………………………………………………8

3.1易腐食品配送现状……………………………………………………………………………………8 3.2存在问题分析…………………………………………………………………………………………9 3.2.1对配送时间没有进行有效规划………………………………………………………………9 3.2.2易腐食品配送成本高…………………………………………………………………………9 3.2.3带时间窗的易腐食品模型应用难……………………………………………………9 3.3易腐食品研究的必要性分析………………………………………………………………………10 4 模型的建立和求解…………………………………………………………………………………………10

4.1条件假设……………………………………………………………………………………………10 4.2参数设置……………………………………………………………………………………………11 4.3模型的建立…………………………………………………………………………………11 4.4求解方法……………………………………………………………………………………………11 4.5案例测算……………………………………………………………………………………………12 4.6算法存在的问题……………………………………………………………………………………16 5 总结…………………………………………………………………………………………………………17 参考文献………………………………………………………………………………………………………18 致谢……………………………………………………………………………………………………19

1

带时间窗的易腐食品配送路径选择问题

[摘要]本文对带有时间窗的易腐食品路径选择问题进行研究，以易腐食品的特性为基础，用运筹学的方法建立了一个适用于易腐食品配送的车辆调度模型，通过运筹学的表上作业法进行求解。将该模型运用于模拟数据中，进行模型的演算。

[关键词]物流；配送；易腐食品；表上作业法；线性规划

Research on vehicle routing problem with time window

of perishable goods distrbution

Zhou Na Department of Logistics Management,school of Management

[Abstract]This paper researches on vehicle routing problem with Time window of perishable goods Dairy Distribution,It bases on the characteristics of dairy distribution,and according to the investigation dada.It has established a wehicle scheduling model suits to perishable goods dairy distribution by Linear rogramming .The model is solved by Tabular method.At last, the model is Calculused by using Simulation data. [Key words] logistics； distribution； perishable goods； Tabular Method ；Linear Programming

2

带时间窗的易腐食品配送路径选择问题

1引言

1.1 研究背景

随着人民生活水平的提高，易腐食品的消费逐年增长，人们对这类食品的安全卫生也提出了更高的要求，这些因素将刺激易腐食品的发展，特别是对易腐食品少批量多品种的配送有很大的需求。2001～2010年，我国易腐货物（主要指肉类、禽类、蛋类、奶类）的运量，将从4900万吨增长到7500万吨，年递增率达到4.8%～5%。公路运输增加较快，其快速发展的同时也促进了货运的发展。2001年公路货运量105.5亿吨，比上年增长1.6%；货运周转量6330.4亿吨，比上年增长3.3%。公路注册载货汽车509.3万辆，其承载质量为1733.6万吨，车辆数比上年增加23.3万辆，增长4.57%；总载质量比上年增加65.9万吨，增长3.8%。专用载货汽车拥有量为12.6万辆，比上年增加1.9万辆，增长17.2%。公路冷藏运输的运量和货物的周转量将会较快的发展[1]。

而在中国公路运输中，冷藏配送只占总量的20%，其余的80%左右的水果、蔬菜、禽肉、水产品大多是用普通卡车配送。由于公路冷藏配送效率低，食品损耗高，整个物流费用占食品成本的70%，而按照国际标准，食品物流成本最高不能超过总成本的50%。迫切的需要对易腐食品配送路径的问题的研究。

1.2 研究意义

易腐食品被公认为各类消费商品中的第一商品，是人们一直的消费热点，其物流配送的市场前景无限光明。在易腐食品的配送过程中，配送路线是否合理直接影响到配送的效益、成本以及服务质量，所以易腐食品的配送路线优化问题一直是国内外学者普遍探索的重要课题。由于消费者的需求不断趋于多样化，对配送的时间的要求也日趋严格，尤其是配送海产品、花卉、蔬菜、奶制品等讲究新鲜度的高时效性易腐食品时，如果配送不及时就会造成其价值的大幅度降低。但是传统的物流配送难以满足易腐食品严格的时效性要求，要改变这种状况，关键是从配送时间上寻求突破。所以，探讨如何改进现有配送方式、尽量缩短配送时间，最大限度地保证易腐食品的配送质量是十分必要的。

在现在实际的物流系统中，许多情况下，客户对车辆的到达时间是有的。但是到目前为止，对货物的调度路径选择问题上很少考虑到对时间的，这方面的研究将会是有益的。按时把货物送到指定地点是最重要的，同时也是最难做到的。在实际运输中，经常出现货物迟到的现象，这对于企业的销售影响很大，甚至因此失去客户。对于冷藏配送来说，不及时送到，对于货物的质量有很大的影响。特别是没有机械制冷装置的运输工具，比较保温汽车，路上运输的时间越长，对货物的影响就越大。所以在配送线路和方式的选择上要注意时间性和距离性。从成本上考虑在配送易腐食品的时候，要从运输方式、运输路线、运量和运距等环节考虑降低运输成本。所以运用数学方法合理地建立适合易腐食品配送的模型，有利降低物流成本和提高客户的满意度。

3

带时间窗的易腐食品配送路径选择问题

基于以上情况，本课题主要研究易腐食品配送的路线优化问题，旨在降低总的配送成本和满足客户所要求的时间，寻找易腐食品配送过程中的最优配送路线。

1.3研究方法

(1)线性规划法

线性规划是指研究线性约束条件下线性目标函数的极值问题的数学理论与方法。即对于统筹规划问题，为如何合理地、有效地利用现有有限的人力、物力、财力资源来完成更多的任务，或者如何才能以最少的代价去实现目标作出的最优决策，提供科学的依据。采用数学语言来描述：问题的目标用变量函数的形式来表达（称为目标函数），问题的条件用有关变量的等式或不等式来表达（称为约束条件）。当变量连续取值，且目标函数与约束条件均线性时，称这类模型为线性规划模型。有关线性规划问题的建模、求解和应用研究构成了运筹学中一个重要的、应用最为广泛的分支。其典型问题有：运输问题、生产计划问题、下料问题、混合配料问题等。

(2) 表上作业法

表上作业法是求解运输问题的一种简便而有效的方法，其求解工作在运输表上进行。它是一种迭代方法，迭代步骤为：先按某种规则找出一个初始可行解（初始调运方案）；在对现行解作最优性判别；若这个解不是最优解，就在运输表上对它进行调整和改进，得出一个新解在判别，再改进；直至得到运输问题的最优解为止。如前所述，迭代过程中得出的所有解都要求是运输问题的基可行解。

常用的表上作业法有：最小元素法、西北角法和沃格尔法。在本论文中，主要采用最小元素法对模型进行求解。

最小元素法：为了减少运费，应优先考虑单位运价最小（或运距最短）的供销业务，最大限度地满足其供销量。即对所有的i和j，找出cij00并将xi0j0min(ai0,bj0)min(cij)，

的物品量由Ai0供给给Bj0。若xi0j0ai0，则产地Ai0的可供物品已用完，以后不再继续考虑这个产地，且的需求量由bj0减少为bj0ai0；如果xi0j0bj0，则销地Bj0的需求已经得到满足，以后不再考虑这个销地，且Ai0的可供量由ai0减少为ai0bj0。然后，在余下的供、销点的供销关系中，继续按上述方法安排调运，直至安排完所有供销任务，得到一个完整的调运方案（完整的解）为止。这样就得到运输问题的一个初始基可行解（初始调运方案）。

由于该方案基于优先满足单位运价（或运距）最小的供销业务，故称为最小元素法。

2理论基础

2.1易腐食品概述 2.1.1易腐食品的定义

易腐食品区别于普通货物的关键是，在一定的温度、湿度条件下，随着时间的推移，

4

带时间窗的易腐食品配送路径选择问题

易腐食品的质量总会有不同程度的、不可逆转的下降[2]。

(1)易腐食品的概念

果蔬类在采摘脱离植株后，肉食品类在原生命体的代谢结束后，在自然环境中、在短时间内极易变质、腐坏的鲜活农副产品统称为易腐食品，如肉、鱼、蛋、奶、鲜水果、鲜活植物等 [3] 。

(2)易腐食品的种类

易腐食品主要包括:蔬菜、水果、鲜花、海鲜及海鲜制品、鲜奶及鲜奶制品、鲜蛋及鲜蛋制品、肉类及肉制品、食用油、酒类、饮料、果酱等 [4] 。

由于易腐食品自身的特性，使其配送时间受到严格容许配送期限的制约。因此，针对易腐食品时效性要求高的特点，切实组织好易腐食品的配送工作势在必行。 2.1.2易腐食品的配送特点

易腐食品因类别和特征不同，其生产及配送过程也有所差别，各类易腐食品具有不完全相同的配送特点。 (1)蔬菜

随着生活水平的提高，人们对蔬菜的质量要求越来越高。新鲜蔬菜容易失水而导致品质降低，所以蔬菜运输的基本要求是小批量、多批次、速度快、运费省、办理运输简便、能保证运输质量。

目前有两种主要的产销结构类型，即以产区(蔬菜生产基地)为中心的外销类型和以较大城市为中心的外购类型，主要流向是由外销中心到外购中心。当外销中心与外购中心相距较近时，物流配送具有较强的竞争力，铁路运输的竞争力相对较小，空运由于批量小一般不会对其他运输方式构成较大影响；当外销中心与外购中心相距较远时，物流配送的竞争力逐渐减弱，水路运输与铁路运输的竞争力逐渐增强；随着距离的进一步增加，水路运输由于速度低而失去优势，铁路运输的优势愈加明显。因此，当外销中心与外购中心相距较近时，蔬菜的配送优势更加明显。

(2)水果

我国水果经营的特点及其对运输方式的要求与蔬菜基本相同，但在时间及地域上水果的产销情况具有其自身的特点，即水果的产销多集中在夏秋季节，有些水果具有基本稳定的流向；有些水果需要进行全国性的流动，销往全国的水果主要有:山东、陕西、河南的苹果，河北、山东的梨，广东、广西、福建的香蕉，广东、海南、广西的菠萝，的葡萄、哈蜜瓜等[6]。

从运输的角度看，过去的大宗水果如苹果、梨、柑桔等常常是远距离跨省运输，铁路运输和水路运输的竞争优势比较突出。而从目前的情况来看，除云南、广西等山区省份外，物流配送不仅在中短途运输中存在优势，在长途运输中也显示出较大的竞争力 (特别是回空运输时)。因此各个季节的水果配送无论其配送距离远近，都表现出非常明显的优势。

5

[5]

带时间窗的易腐食品配送路径选择问题

(3)肉类

肉类对运输的要求主要是低温、批量适中、载量大、速度快、运费省等。过去较长距离的肉类运输一般由冷藏车在低温下进行，由于汽车装载量有限且运费相对较高，因而铁路冷藏运输具有较好的市场竞争力。近年来物流配送的发展很快，其在肉类冷藏运输市场上所占的份额也逐步扩大，如运往广东和北京的肉类因为物流配送回程车的运费低、手续简便、配送速度快、运价灵活等原因而选择物流配送的运输方式。据统计，1997年四川省经铁路的肉类运输占鲜活易腐货物比例的73%, 1998年己迅速下降为55%，而且其比例仍然在继续下降[7]。

因此，可以看出在肉类的运输过程中，配送所占的市场份额越来越大，尤其在中 短途的运输中，物流配送的优势表现得越发明显。

(4)海鲜

海鲜对运输市场的要求主要是鲜、活、快且能承受较高的运输费用。海鲜的运销有多种方式，山东省的海水养殖产品主要在产地自销，海洋捕捞的鲜活海水鱼采用航空运输的方式运往北京、天津、济南等大城市，淡水鱼中有一部分经加工处理后也采用航空运输的方式运往韩国，新鲜海水鱼经冷冻后主要由铁路冷藏车运输。高档海鲜通常采用航空运输，铁路在运输市场中所占的份额较小且主要针对于长途运输，而中短途的接驳运输几乎完全依赖于物流配送[8]。此外，广州还出现了生产、运输、加工一条龙的现象，这种供应链主要通过物流配送来衔接。

可见，海鲜因其要求鲜、活、快的运输服务而使物流配送在中短途运输中占尽优势，尤其是高档海鲜的中短途接驳运输几乎完全依赖于物流配送。

综上所述，蔬菜、水果、肉类及海鲜这四类典型的易腐货物由于自身特征不同，其配送过程也存在明显的差别。但从总体来看，易腐食品运输因其要求鲜、活、快的运输服务而使物流配送在中短途运输中占尽优势，尤其是高档海鲜产品的接驳运输几乎完全依赖于物流配送；因为物流配送回程车的运费低、手续简便、配送速度快、运价灵活等原因，使物流配送不仅在中短途运输中存在优势，在长途运输中也显示出较大的竞争力。因此，物流配送在易腐食品的运输中所占的市场份额越来越大，其优势也表现得越来越明显。 2.1.3易腐食品的配送条件

易腐食品因其极易腐坏变质的特性而要求配送过程满足一系列的条件，其中最重要的条件是温度条件。

(1)易腐食品配送的温度条件

造成易腐食品腐烂的主要原因有微生物的作用、呼吸作用和化学作用，这些原因往往不孤立的而是相互影响的，而且一般都与温度条件有关。控制好配送过程中的温度的条件可以增强易腐食品的抗病性和耐藏性。

我国对易腐食品配送季节的划分不是采用气象学的方法，而是根据易腐食品的配送要求按照一系列的平均气温来划分，即平均气温在20℃以上为热季；平均气温在1-19℃为

6

带时间窗的易腐食品配送路径选择问题

温季；平均气温在0℃以下为寒季，，其中温季可以继续细分为10C-60C ,70C-12℃及30C-19℃三个温季段[9]。根据不同品类易腐食品送时具体的温度要求，可以采用相应的配送方式。

由于我国幅员辽阔、南北温差很大，在选择配送季节和配送方式时不但要考虑出发地的气温还要考虑沿途气温及目的地气温，以确定全程或分段的配送季节。例如，秋冬季节从东北、华北地区配送水果到华南地区，在出发地一般不用加冰制冷，但送到郑州以南就要开始加冰制冷；冬春季节由南方地区配送蔬菜到东北、华北及西北地区，在出发地需要加冰制冷，送到北方就需要考虑保温防寒的问题。 (2)易腐食品配送的基本条件 易腐食品配送的基本要求如下:

①不同热状态的易腐食品不能按一批配送。为了保证易腐食品的配送质量，按一批办理配送的易腐食品的配送条件和所采用的配送方式应当相同。

②配送易腐食品时应在货物运单上的“货物名称”栏内填记货物的名称，并注明其品类顺号、热状态及容许配送期限，容许配送期限必须大于所规定的运到期限三日以上方可承运。

③配送易腐食品时，货物的质量、温度、包装和选用的配送车都要符合“易腐食品配送条件表”和“易腐食品包装表”的规定。

综上所述，必须满足易腐食品配送的所有条件才能保证货物的送到质量，提高配送的服务水平。此外，也可以通过提高配送速度来减少易腐食品的在途的配送时间，以降低其配送过程中的腐坏程度，从而最大限度地保持货物的质量[10，11] 。 2.2时间窗概念

时间窗就是配送车辆希望完成服务而顾客希望接受服务的时间范围，根据时间窗约束的严格与否，可分为软时间窗和硬时间窗。

在进行易腐食品的即时配送时，必须在客户要求的时间窗内完成配送任务，根据客户所要求时间窗约束的严格与否，可分为软时间窗的易腐货物即时配送路线优化问题和硬时间窗的易腐食品即时配送路线优化问题。 2.2.1硬时间窗

硬时间窗是指如果配送车辆无法将易腐食品在要求的时间窗内送到客户手中，则必须按照违反时间的长短施以一定的罚金或其他惩罚措施；硬时间窗的特点是模型存在数值无穷大的可行解，可以视为模型不存在可行解。 2.2.2软时间窗

软时间窗是指每项任务必须在要求的时间窗内将易腐货物送到客户手中，无论迟到还是早到都不予接受。若超出时间窗范围，反映到模型上时，软时间窗的特点是模型存在数值较大的可行解。

7

带时间窗的易腐食品配送路径选择问题

3现状分析

3.1易腐食品配送现状

物流作为企业的“第三利润源泉”,备受关注。在得知物流业有可观的发展前景之后,上到下到企业都纷纷探讨如何提高物流利润,使其成为一个重要的发展行业。通过分析研究发现:配送成本在物流的各项成本当中占有相当高的比重,因此对配送中心而言,合理的整合配送业务流程和优化配送路径不仅可以简化配送程序、减少配送频率,而且更重要的是可以降低配送费用,从而带来更大的效益,因此配送路径的优化选择引起了各界人士的注意，是目前迫切需要解决的问题。

⑴易腐食品的配送基础设施建设方面的情况。

易腐食品的冷冻硬件设施滞后，现代化的冷冻冷藏车严重不足。目前运营中的冷冻、冷藏运输设备陈旧，制冷技术和工艺落后，缺乏规范式的保鲜冷藏运输车厢和温度控制设施，无法为易腐食品配送提供低温保障，造成配送运输中的极大浪费，费用占到易腐食品成本的70%。

⑵易腐食品配送与其上游和客户的情况。

易腐食品在进行集货时，缺乏和上游企业进行沟通和制定相关的合同和措施，使得货物没有及时的送到配送中心，造成后面配送时间的紧迫，不能有效率地进行配送，食品往往在运输途中变质，不能满足消费者的需求。而在客户方面没有及时沟通，则订单和路径规划没有得到很好的协调，一般都是有订单就调货发货，整个过程没有规范化，配送的效率极低，物流的成本一直居高不下，造成易腐食品的价格也持高。

⑶易腐食品在配送时间和成本的情况。

易腐食品配送如何降低配送成本是研究易腐食品配送问题的主要因素。在时间上满足客户的要求也是在配送时要考虑的第二大因素，调整好这两个目标对真正降低总成本，提高客户满意度有重要的作用。但是到目前为止，对货物的调度路径选择问题上很少考虑到对时间的。

首先，在配送路线的选择上易腐食品配送中心只是根据传统的有订单立即送货的模式，没有根据订单对配送路线做规划，采用数学的方法解决配送问题，使得市场价格持高不下，影响了消费者的消费水平，不能最大限度地满足消费者的需求。

其次，在易腐食品的运输过程中，配送中心没有选择好相应的运输工具或是缺少相应的冷藏措施，只是采用较为简单的保鲜措施，使得配送的完好率下降。增加了配送环节的费用。

再次，在时间窗方面，配送中心没有对路线进行具体的规划和订单规划，在配送时常常是什么时候来订单什么时候配送，较为先进一点的配送中心就是有一个相对固定订货期，先集货，然后进行配送，这能稍微提高配送的满载率降低运输成本。配送中心在装卸搬运时，没有合理规划装卸搬运的作业时间，使得易腐食品在装卸搬运时，耽误了许多时间，使整个配送时间大大的增加。从第四章的模型可以看出，装卸搬运时间在整个配送时

8

带时间窗的易腐食品配送路径选择问题

间中占了大半的时间，所以合理规划装卸搬运的作业时间对减少易腐食品在空气中暴露的时间，保持易腐食品的完好性，满足客户的时间要求，降低易腐食品配送费用，有决定性的作用。

虽然在数学上运输路径的选择问题早有了相关的理论和研究成果，但带有时间窗的配送路径选择问题仍然是个盲点，特别在实际配送中相关理论的运用处于有待发展的阶段。

那么配送中心对时间窗规划和降低配送环节的物流成本，是本论文在模型建立时要考虑的主要问题。

3.2存在问题分析

3.2.1对配送时间没有进行有效规划

易腐食品往往在配送的时候只考虑配送成本最小，没有考虑到时间窗问题。往往当货物运到客户时，配送中心只能拿到70%的费用，因为没有针对每个易腐食品的特性规划该类食品最佳的配送时间，所以在送到客户手中的只有70%的货物完好，其30%在配送途中腐烂了。

另外在装卸搬运时也没有进行作业时间的规划和控制，装卸搬运作业速度快慢也是影响到后来总配送时间的因素。往往整个配送时间绝大部分是发生在装卸搬运上，把装卸搬运时间和配送时间结合在一起的总配送时间来考虑，是有实际意义的。

所以如何针对此类问题建立相关模型成了本论文的重点。好的配送不仅是送到货，满足客户的要求，更重要的是完好的把货物送到客户手中。在本论文的模型建立中，会针对这个问题设一个时间的参数。 3.2.2易腐食品配送成本高

易腐食品和一般的食品不同。首先，它具有的极易腐坏变质的特性，要求在配送要有低温的配送设施，如冷藏车等，在车辆的花费上要比一般货物费用要高。其次，在路线的规划方面不只是一味考虑最小成本，还要考虑易腐食品腐坏的时间和客户要求的时间。这就增加路线的迂回继而配送的总费用。再次，在装卸搬运方面的为了加快速度减少时间，会增加装卸搬运人数，这就增加了配送成本。 3.2.3带时间窗的易腐食品模型应用难

在模型的建立中要考虑到多个目标，时间、还有车辆的装载量，配送路线的路况，配送路线车辆的数目，配送路线的距离等。因而建立带有时间窗的模型时有一定的难度，考虑的因素众多，参数设置也多，在建立易腐食品配送模型特别复杂。在该模型算法的求解上也很复杂，要用到人工智能相关理论去解决，有遗传算法和禁忌搜索算法等。在本论文中只考虑其中自主要的两个因素：时间和成本，降低了模型的难度。但是在模型建立时有了许多假设条件，是模型的运用在一个特定的条件范围中，这是不足之处。

3.3易腐食品研究的必要性分析

9

带时间窗的易腐食品配送路径选择问题

易腐食品配送路线优化的必要性有两个方面： ⑴时间的必要性

在研究易腐食品配送路线时，要从时间这个决定因素考虑，选择和制定配送路线。配送时间主要依据易腐食品装卸搬运时间和车辆运输时间来决定。在常温下易腐食品随着时间的推移，会不同程度地发生不可逆转的腐坏。这类食品要求配送时间尽可能的短，从时间上来减少易腐食品的概率。

所以易腐食品配送模型考虑到时间是必要的。 ⑵成本的必要性

每个企业最大的营业目是增加盈利，降低成本。配送企业也不例外，降低配送成本是其首要考虑的问题。易腐食品配送成本主要由配送的装卸搬运成本和运输成本构成。如何在易腐食品配送中降低各个成本，设计最小成本路线是配送企业最关心的问题

所以易腐食品配送模型建立考虑到成本是必要的。

时间和成本因素相互影响，容易出现配送不及时、配送子路线选择不恰当，耽误交货时间等问题。全面考虑各种因素对于配送方案的优化设计和降低成本是相当关键重要的。这是成本的必要性。

所以模型在设计时要综合考虑这两个要素：时间和成本，如何调整时间和成本的关系，建立一个合理的运输方案是本论文的重点，在第四章会重点介绍。

4模型的建立和求解

4.1条件假设

在本论文中，只假设有成本和时间两个目标。

⑴第一个目标是运输时间准时，第二个目标是总的费用最小。货物能否按照客户要求的时间T准时运到客户手中是判定准则。

⑵供需特征满足确定型的特点。这是指物品供应需求量已知的，并在一定时间内相对稳定。

⑶设施的数量为多个。

⑷车辆装载能力是确定型。这是指对这个问题所涉及的每条路线的货物总量很小，不会超出车辆的装载量，因此，不用考虑车辆的装载能力的。

⑸设施是车辆路线的出发点又是终点。 ⑹配送中心的供给量大于客户的需求量。

⑺用同一种运输工具完成所有运输量,总运距最短(费用最少),即所需时间最短。按传统运输问题的表上作业法进行求解,所得结果若满足时间约束tT,该解即为满足时间条件的最优解。若不满足时间约束tT,则该问题没有解。这是因为用传统运输问题的表上作业法所求的最优解,是费用最小的解,费用最小的解也就是总运距最短的解,即所需的时

10

带时间窗的易腐食品配送路径选择问题

间最短的解。不满足时间约束tT,则说明该运输问题的最短时间仍大于时间约束值T,故该问题无解。

⑻假设Ki为1。

⑼xij的货物用一辆车运输。

4.2模型中的参数含义：

f——表示总费用；

xij——表示供应点i到需求点j的实际供货量；

T——表示客户所要求的到达时间；

tij——表示从配送中心i到客户点j的所用的时间；

Ki——表示发点i的装卸速度； tij——表示从发点i到收点j的运输时间； cij——表示发点i到收点j的单位运价。

4.3模型的建立

目标函数为：

minfcijxij

i1j1mn约束条件：

xi1nmijAi,i1,2,,m

xj1ijBj,j1,2,,n

xij0

约束时间具有并联特性的运输问题(即各发点同时开始装运货物),整个调运所需时间t(约束时间)取决于装运货物所需时间最长的一个发点到收点所需的时间,而各发点到各收点装运货物所需时间只取决于该发点的发量和到收点运输时间tij。则发点i到收点j的调运时间tij为：

nxijj1tijtij ，在表上可表示为：

Ki* 11

带时间窗的易腐食品配送路径选择问题

表1：模型 需地 供地 x1 c11 c12 c12  x2 c12 c12 c12  x3 x4 c12 c12 c12    xn c1n 供给量 A1 A2 A3  p1 p2 p3  c12 c12 c12     c12 c12  pm cm1 cm2 cm3 B3 cm4   cmn An 需求量 B1 B2 B4 Bm 其中A1A2A3AnB1B2B3Bm

4.4求解方法

运用表上作业法求解此类问题。

表2最小元素法求初始方案 需地 供地 x1 4 x2 x3 x4 供给量 ⑾ 9 ⑹ 16-10-6 10-8-2 22-14-8 48 p1 p2 14 14-14 12 10 ⑸ 10 2 12-2-10

⑷ ⑶ 11 6 8 14-8-6 8 ⑵ 8 p3 8-8 需求量 表3检验数表 需地 供地 x1 x2 x3 x4 供给量 p1 p2 p3 1 10 2 1 12

12 -1 需求量

带时间窗的易腐食品配送路径选择问题

由于2410，所以这个初始方案不是最优解，用x24为换入变量，得到新的基可行解见表4。

表4调整后的量 需地 供地 x1 x2 x3 x4 供给量 16 10 22 48 p1 p2 p3 8 8 14 14 10（+2） 2（-2） 12 6（-2） （+2） 8 14 需求量 在对新的基可行解进行检验，见表5。

表5新的检验数 需地 供地 x1 x2 x3 x4 供给量 p1 0 9 2 2 1 12 p2 p3 需求量

由于所有的检验数都为正数，所以这个解为最优解。其运输方案是p1运12单位到x3，4个单位到x4；p2运8个单位到x1，运2个单位到x4；p3运14个单位到x2，运8个单位到x4。

总运费为f124411822914586244

i1j134最小损失闭回路调整法求解时间约束条件：

最小损失闭回路调整法是指:用运输问题的表上作业法所求解的结果不满足时间约束调整步骤:

①列出求解运输问题的运输时间表。

②按照传统的运输问题的表上作业法,计算该运输问题的最小费用。

③计算运输时间tmaxxij(i=1,2, …,m；j=1,2, …n) 。假如t≤T ,则得到最优解,输出结果,结束。否则,进行④。

④用最小损失闭回路调整法进行调整。

调整方法如下:首先按照下标从小到大的顺序选取第一个调运时间tij大于时间约束值 T 的项,例如此项为xij。然后从所有与基变量xij不在同一行、不在同一列的基变量中选取一个基变量xgh,要求tgi和tih不能大于时间约束值T,并且使得cgi+cih-cij-cgh的值为最小,即

13

条件时,用最小费用损失换取时间超值下降的一种调整法。下面说明最小损失闭回路法的

带时间窗的易腐食品配送路径选择问题

使得式子cgi+cih-cij-cgh的值在所有与基变量xij不在同一行、不在同一列的基变量中是最小的。

接着令minxij,xgh

xijxij

xihxih xghxgh

xgixgi

⑤观察xij是否为0。假如xij为0。则转到③；否则转到④。

从上面的调整方法可知,闭回路是由两个基变量xij和xgh作为对角点所围的一个矩形。其中至少有一个基变量xij是超时点,即tijT；而它的对角点g,h是货物调运数大于0的点 tgh0。cgi + cih - cij - cgh可保证每次因降低时间而加上的费用代价是最小的。最小损失闭回路法的主要思想:通过加上最小的费用值以降低运输问题所需的最短时间,从而使其满足时间约束条件 tT。故当tT时,用最小损失闭回路法进行调整,所得到的解是满足时间约束条件tT的最小费用解。

4.5 案例测算

p2,p3,p4)例子：有4个地区(x1,x2,x3,x4)急需一批水果,现欲从4个配送中心(p1，

调运,各地区需要的水果数量、各配送中心提供的数量,以及从各配送中心到各客户点的费用(运价单位:千元/ 吨)如表6所示,从各配送中心到各客户点的时间如表7所示，那么如何运输才能保证在40 h以内将客户需要的水果在尽可能小的费用送到各地区?

表6单位运价表

需地 供地 x1 x2 x3 x4 供给量 30 35 30 20 p1 3 1 7 3 30 11 9 4 2 40

3 2 10 7 20 10 8 5 10 25 p2 p3 p4 需求量 表7运输时间表

x1 x2 x3 x4 p1 p2

10 10 2 3 14

8 9 3 4 带时间窗的易腐食品配送路径选择问题

p3 6 20 15 13

表8调运时间表

13 9 4 11 p4 需地 供地 x1 x2 x3 x4 p1 p2 p3 40 45 36 40 32 38 45 43 38 44 43 29 33 39 34 31 p4

解:第一步，先算出其调运时间表,如表8所示。

第二步，再按照表上作业法算出最优解如表9所示(运量单位:吨) 。 第三步，计算总的最小费用为40万元。

第四步，方案的时间与客户要求的时间进行比较，可以看出时间t21t3245h，大于客户要求的时间40h，不满足时间约束条件,则需用最小损失闭回路法进行调整。

表9运输表上作业法的调运量 需地 供地 x1 x2 x3 x4 供给量 30 35 30 20 t/h 40 45 45 33 p1 p2 p3 10 20 30 20 20 40 20 20 15 10 25 p4 需求量

按照下标从小到大的顺序选取第一个大于40 h的项x21，然后进行调整。和x21不在同一行，同一列的基变量有x13、x32、x34、x42。

对基变量x13,由于t234440,因而不满足要求。 对基变量x32,算得c22c31c21c32971411 对基变量x34,算得c24c31c21c3487159 对基变量x42,算得c22c41c21c4293129

所以选基变量x42对基变量x21进行调整。这时minx42,x2120 ,调整的结果如表10所示(运量单位：吨) 。

15

带时间窗的易腐食品配送路径选择问题

表10经一次调整后的调运量 需地 供地 x1 x2 x3 x4 供给量 30 35 30 20 t/h 40 39 45 40 p1 p2 p3 10 20 30 20 20 40 20 20 15 10 25 p4 需求量

运费在原费用的基础上又增加18万元。由于这个方案t3245h,所以不满足客户对时间的为40h的要求,继续进行调整。与基变量x32不在同一行、同一列的基变量有x11、x13、

x24和x41。

对基变量x11,算得c12c31c11c321173411 对基变量x13,由于t334340,因而不满足要求。 对基变量x24,算得c22c34c32c2495482 对基变量x41,算得c31c42c32c4172432

所以基变量x41对基变量x32进行调整。此时minx41,x3220,调整的结果如表11所示。

表11第二次调整后的调运量 需地 供地 x1 x2 x3 x4 供给量 30 35 30 20 t/h 40 39 33 p1 p2 p3 10 20 30 20 20 40 20 20 15 10 25 p4 需求量

这个方案的运费在原费用基础上又增加4万元。这方案需要的时间为t1140h,满足客户要求的时间。所以表11的方案可在40h内将油料运到各地区,此时的费用最小为62万元。（如果模型计算时调整的顺序不同,所得的最优解不相同,即最优解不唯一,但算得的最小费用一样。）

4.6算法存在的问题

模型应用的局限性,由于模型的建立中有许多假设条件，是在只用一辆车完成配送任务，装卸搬运速度假设为1，供货量大于需求量等一系列假设条件的前提下建立的模

16

带时间窗的易腐食品配送路径选择问题

型。所以只适用于一小部分配送调度问题。

随着以后条件的减少，问题研究对象的增多，模型会越来越复杂，以后会形成多目标的特征，对多目标的调度问题是我们以后要研究的方向。而针对适合大规模的配送调度问题，可以运用与人工智能相关的一些算法求解，例如智能优化算法、遗传算法、禁忌搜索算法等来研究多目标求解的算法问题。

5总结

在本论文中，根据易腐食品的特性、运输特点、运输条件和时间窗等条件来对易腐食品建立可以在一定条件下可行的模型。运用已学的运筹学应用到建模和求解此模型的算法上，在模型的建立中运用了线性规划法，在模型的求解上运用表上作业法来对模型进行求解。由于建模有一些假设条件，所以在此模型的应用上有一些局限性，不过随着研究的深入运用到多目标模型和人工智能等方面的理论知识时，可以对模型进行改进。

17

带时间窗的易腐食品配送路径选择问题

主要参考文献：

[1] http://www.cb-h.com/news/spdb/2008/410/08410112626055JKJKIKB502I2KCA9B.html [2] http://jpkc.shiep.cn/ssc/ycx/cd.htm

[3] 铁道部《鲜规解释》编写组.铁路鲜活货物运输规则解释(节选)[J].铁道货运,1995,3:52- [4) 铁道部《鲜规解释》编写组.铁路鲜活货物运输规则解释(续五)[J].铁道货运，1996,3:52- [5] 顾霄勇，高亦兵.易腐食品知多少[J].消费者之友，1995,9:36

[6] 谢如鹤，王俊，罗荣武，李夏苗，李绍荣·易腐草物冷藏运输的市场需求分析[J].铁道货运，2003,1:18-20

[7] 罗荣武，谢如鹤.铁路易腐货物运输工具发展趋势当议[J].中国铁路，1999,11:12-15 [8] 谢如鹤，叶德春.鲜活易腐食品的“保鲜链”[J].冷藏技术，1996,74:41-42 [9] 中国商业年鉴[Z].北京:中国农业出版社，2000

[10] 铁道部《鲜规解释》编写组.铁路鲜活货物运输规则解释(续13 )[J].铁道货运，1998,1:52-53 [11] 铁道部《鲜规解释》编写组.铁路鲜活货物运输规则解释(续15 )[J].铁道货运，1998,3:50-53 [12] 中国统计年鉴[Z].北京:中国统计年鉴出版社，2000

[13] 邹俐宏.温度对易腐果蔬贮运质量的影响及控制[J].长沙铁道学院学报，2002,20(6):62一65 [14] 国内贸易部食品流通开发委员会.生鲜食品物流冷链系统关键技术及综合示范工程(“九五”国家重点科技攻关项目报告)[R].1997

[15] 李绍荣.铁路易腐货物运输的市场分析[J].冷藏运输，2003, (5):23-26铁道部《鲜规解释》编写组.铁路鲜活货物运输规则解释(续二)[J].铁道货运，1995,6:47-52

[16] 运筹学教材编写组.运筹学(修订版)[M].北京:清华大学出版社,1997. [17] 胡运权.运筹学基础及应用[M].哈尔滨:哈尔滨工业大学出版社,1993. [18] 李书涛.决策支持系统原理与技术[M].北京:北京理工大学出版社,1996.

18

带时间窗的易腐食品配送路径选择问题

[19] 马绍民.综合保障工程[M].北京:国防工业出版社,1995.

19