制造型企业的产品配送车辆路径优化问题

第一章 绪论
1.1 课题研究的背景及意义

物流在电子商务中具有不可替代的作用,它的成功与否直接关系到电子商务的成败,它的实施与运作效率将直接影响网络所带来的经济价值。物流(logistics)是供应链中最重要的组成部分,是商品从生产者经过诸流通环节最终到达消费者手中的过程。物流业则是专门从事物流活动的行业,从企业销售成本和商品价格组成角度考察,物流业蕴藏着巨大的商机。现代物流业已被公认是企业在降低物资消耗、提高劳动生产率以外的“第三利润源泉”,也是企业降低经营成本,提高产品竞争力的重要途径,因而受到国内外各行业的极大重视,并得到较快发展。大量经营规模较大的制造企业和商业企业纷纷建立起配送中心,向商品流通效率化发起挑战,与此同时,相当部分的大型运输、仓储和航运企业开始转向第三方物流经营。
物流配送是物流活动中直接与消费者相连的环节。在物流的各项成本中,配送成本占了相当高的比例。物流配送车辆调度优化,是物流配送优化中关键的一环,也是电子商务活动不可缺少的内容。配送车辆调度的合理与否对配送速度、成本、效益影响很大,特别是多用户配送车辆调度的确定更为复杂。采用科学、合理的方法来进行配送车辆调度,是物流配送中非常重要的一项活动。对货运车辆进行调度优化,可以提高物流经济效益、实现物流科学化。对货运车辆调度优化理论与方法进行系统研究是物流集约化发展、建立现代调度指挥系统、发展智能交通运输系统和开展电子商务的基础。目前,问题的形式已有很大发展,该问题已不仅仅局限于汽车运输领域,在水运、航空、通讯、电力、工业管理、计算机应用等领域也有一定的应用,其算法已用于航空乘务员轮班安排、轮船公司运送货物经过港口与货物安排的优化设计、交通车线路安排、生产系统中的计划与控制等多种组合优化问题。
运输问题是物流决策中的关键问题。一般来说,除去产品中的采购成本外,运输成本比任何其他物流活动的成本所占的比例都要高。尽管运输的形式有很多种,但其中最重要的不外乎运输方式的选择、车辆路径的选择与规划等内容。本文将针对其中的车辆路径问题作较深入地探讨。
选取恰当的车辆路径,可以加快对客户需求的响应速度,提高服务质量,增强客户对物流环节的满意度,降低服务商运作成本。正是有这种迫切的需求,所以在计算机高度发展的今天,如何让计算机模拟物流的配送过程,并最终给出最简洁最高效的配送方案,一直以来是众多计算机学者研究的焦点,并由此衍生出了一个新的研究课题──车辆路径问题(Routing Vehicle Problems,VRP)。
车辆路径问题是一个典型的组合优化问题,是一个 NP 难题。问题的目标是:如何利用有限数量的车辆实现客户对物品的配送需求,每个客户被且只能被访问一次,每次车辆的运输距离总长度不超过其最大行驶距离,同时车辆所运送物品的重量不能超过其最大的载重量的限制,目标是使配送成本最小。车辆从配送中心出发,最后要回到配送中心,每辆车的配送路径形成一个回路。如果客户对物品的配送有一定的时间限制,即要在一定的时间窗内来完成运输配送,则问题被称之为有时间窗的车辆路径问题(Vehicle Routing Problems with Time Window,VRPTW)。本文所研究的就是有时间窗的车辆路径问题。在下文中,在没有特指的情况下,车辆路径问题的研究都是针对有时间窗约束条件下的车辆路径问题。
1.2 国内外车辆路径问题问题的研究现状

近年来,随着高性能计算机的迅速发展,国外应用计算机及现代数学方法调度车辆以优化运输管理效果的研究工作,正在较大范围内展开。在车辆调度的形式、构造、分析以及求解方法的实现上都有了许多突破,某些常用且较成熟的算法己被人们运用于实际配送调度系统。据资料显示,美国利用最短路算法、启发式算法开发出计算机配送调度系统,用来解决货运汽车作业计划中路线选择和车辆分配(如选择车型、确定车数和货运点停靠顺序)等问题,使汽车里程利用率提高 5-15%,运输成本和运输时间也有了明显下降;另外美国还采用扫描法开发出车辆调度系统;日本采用节约法开发出配送运输调度系统。
但是,国内在这方面的研究大多数停留在理论层次上,实际应用系统的开发才刚刚起步。随着物流配送业的兴起,对货运车辆运输调度提出了经济性、准时性、灵活性的综合要求。虽然理论界和物流企业界早在数年前就提出建立配送中心车辆调度系统,但时至今日,在开发实用的计算机车辆配送优化调度系统上还是一片空白。主要原因在于:①配送运输在我国还未真正开展,企业对优化调度认识还不够,②车辆调度数学模型本身与配送应用结合上也存在一些问题,大多数算法设置了许多假设,且仅考虑了车辆优化调度问题的某些约束,而实际配送时,用户对运输的要求较高,调度约束条件多,这样就限制了算法的应用范围。
与国际上相比,国内对 VRP 的研究相对较少,有关车辆路径问题的研究是在 20 世纪90 年代以后才逐渐兴起的,比国外相对落后 30 余年。目前,国内对于复杂的车辆路径问题的研究尚处于起步状态,最近几年才陆续有一些相关的研究成果发表:李军和郭耀煌等用传统启发式算法解决了一些相对简单的 VRP 问题,如送货点比较少的容约束、时间窗约束 VRP;蔡延光用遗传算法、模拟退货算法等研究重载 VRP,取得了一些成绩;张涛等通过遗传算法来保证搜索的全局性,用 3-OPT 算法来加强局部搜索能力,得到针对VRP 的混合算法 ;谢秉磊、郎茂祥等用遗传算法在容量约束和时间窗约束的 VRP 上做了一些工作。在综述方面:汪寿阳等对寻址路径问题的研究进行了分析;祝崇隽较全面的回顾了 VRP 领域的最新进展[17];谢秉磊、郭耀煌等对动态 VRP 的最新发展作了评述[18]。随着顾客需求的变化运输车辆的调度显得日益重要,近年来,我国理论界逐渐开始关注车辆路径问题的研究,并已取得初步成果,总体来说,目前我国对车辆路径问题的理论仍需要进一步研究。

第二章 配送车辆路径优化问题
理论概述
2.1 VRP描述
VRP的一般描述是对一系列给定的客户送货点或取货点,确定适当的配送车辆行驶路径,使其从配送中心出发,有序的通过它们,最后返回配送中心,并在满足一定的约束条件下如车辆载重量、客户需求量、时间限制等,使总运输成本达到最小如使用车辆数最少,车辆行驶路或时间最短等
一般而言,车辆路径问题需要从以下几个方面描述
(1)道路网
用来运输货物的道路网通常用一个图来表示,其中,图中的弧用来表示路段,而点则对应于道路交叉点、车场配送中心和客户。根据其道路是单行线还是双行线,相应的弧可以分为有向弧和无向弧。每条弧对应着一个费用,通常表示其距离,或运行时间
(2)客户
用图上的点表示,客户所需运送或收取的货物,可能有不同的品类。一般要求提供服务的时间段时间窗,例如由于客户只在特定的时间段内营业,或者因为交通管制只能在特定的时间段内前往需要估计在客户点交付或提取货物所花费的时间分别为卸货或装货时间。
车场
(3)车场
服务各客户的车辆行驶路径开始并终止于一个或多个车场,车场也用道路图中的点来表示。每个车场的特征由所配备的车辆种类和数量、以及所能处理的货物总量来表示。
(4)车辆
货物的运输由一组车辆来完成,其典型的特性为车辆的配属车场,完成任务后是否要求返回配属车场车辆的容量,通常以最大的载重量、或容积、或可装载的托招数来表示可用于进行货物装卸的设备车辆使用费单位距离、单位时间、每辆车或每条线路等。
(5)路径编排中的限制条件
给配送车辆编排行驶路径时,应满足几个取决于所运送的货物性质、服务质量水平、以及客户和车辆的特点的运营限制条件。诸如,每条线路上,相应车辆的当前装载量不能超过车辆的载重量客户只要求送货、取货、或取送货兼有只能在客户所要求的时间窗以及相应车辆驾驶员的工作时间内给客户提供服务。
(6)行驶费用和行驶时间
为了评价一组配送线路的总费用和检查其相应的运营限制,必须知道客户与客户之间,车场与客户之间的行驶费用和行驶时间。
(7)目标
车辆路径问题通常需要考虑以下几个目标:
①最小化总运输成本,其大小取决于服务所有客户所需要的车辆或驾驶员数、总行驶距离或总行驶时间和与所使用的车辆及其驾驶员有关的固定费用
②均衡各线路上的行驶时间和车辆载重量
③最小化与客户不完全服务等有关的惩罚值或者是这些目标的任何加权组合

2.2 VRP分类
基本卫是指除了车辆的能力约束外,没有其它约束的。但随着物流配送的发展,基本的已不能满足需求,在现实情况下,物流配送所考虑的约束条件逐渐增多,问题也变得更加复杂,从而产生了新的有约束条件的,常见的分类有以下几种·
按物流中心的数目分,有单物流中心问题(配送系统中仅有一个物流中心)和多物流中心问题(配送系统中存在多个物流中心)。
按车辆载重状况分,有满载问题(由于客户需求或供应的货物数量大于或等于车辆的载重量,故完成一项配送任务需要一辆及其以上的配送车辆,配送车辆需满载运行)非满载问题(由于一部分客户需求或供应的货物数量小于车辆的载重量,造成一些配送车辆需要满载运行,而另一些车辆则经常处于不满载状态。)
按配送任务特征分,有纯送货问题(仅考虑从物流中心向客户送货,也成为纯卸货问题)或纯取货问题(仅考虑把各客户供应的货物取到物流中心,也称为纯装问题)及取送混合问题(考虑将客户需求的货物从物流中心送到各个客户,同时考虑将客户供应的货物从客户取到物流中心,也称为装卸混合问题或集取货和送货一体化问题。)
按客户对货物取送时间的要求分,有无时间限问题(客户对货物的取走或送到的时间无具体要求)和有时限问题(客户要求将需求的货物在规定的时间窗内送到,将供应的货物在规定的时间窗内取走,也成为有时间窗问题)。有时限问题又可以分为硬时间窗问题(客户要求货物必须在规定的时间窗内送到或取走,不能提前也不能拖后)和软时间窗问题(客户要求将货物尽量在规定的时间窗内送到或取走,但也可以提前或拖后,只不过在提前或拖后时,要对配送企业实施一定的惩罚)。
按车辆类型数分,有单车型问题(所有配送车辆的载重量相同)和多车型问题(配送车辆的载重量不完全相同)。
按车辆对车场的所属关系分,有车辆开放问题(即车辆完成配送任务后可以不返回其发出车场)和车辆封闭问题(车辆完成配送任务后必须返回其发车场)
按优化目标数分,有单目标问题(仅考虑一个配送目标)和多目标问题(同时考虑多个配送目标)。
2.3 VRP求解
VRP被提出来后,对其求解算法的研究一直是研究的重点和难点。在对其求解算法进行研究的同时,不少学者也对它的计算复杂性进行了研究,为确定求解算法的研究方向奠定了基础。VRP之所以引起学术界的极大重视,除了它具有广泛的应用背景外,因为其相当难解,从而富有挑战性。由于VRP是NP-Hard问题,其相应的精确算法的计算量一般随着问题规模的增大呈指数增长,在实际中的应用范围很有限。VRP是著名的TSP的一般化,不仅约束条件更加复杂,而且要对多条车辆行驶路径进行优化,因此,其计算量比TSP要大得多。
车辆调度问题自提出到现在研究者己经给出了很多求解算法。下面对主要的算法进行概述。
(1) 精确算法
精确算法指可求出最优解的算法,主要有分枝定界法、割平面法、网络流算法、动态规划法。精确算法的计算量一般随问题规模的增大而呈指数增长,所以多用于规模较小的问题。
(2) 启发式算法
启发式算法而加是相对于最优化算法提出的。在某些情况下,特别是实际问题中,最优算法的计算时间使人无法忍受,或因问题的难度使其计算时间随问题规模的增加以指数速度增加,如问题,此时只能通过启发式算法求得问题的一个可行解。面对的难解现实,专家们基本上都把主要精力集中在构造高质量的启发式算法上。年至年间,所提出的启发式算法都是基于经典的启发式方法的思想。目前己提出的启发式算法很多,分类也相当多,但主要有以下两种
1) 构造算法
根据一些原则,每一次将一个不在线路上的点增加进线路,直到所有的点都被安排进线路为止。该类算法的每一步,把当前的线路构形很可能是不可行的跟另外的构形也可能是不可行的进行比较并加以改进,后者或是根据某个判别函数例如总费用会产生最大限度的节约的构形,或是以最小代价把一个不在当前构形上的需求对象插入进来的构形,最后得到一个较好的可行构形。如一节约算法、插
入法'〕。这类方法一般速度快,也很灵活,但这类方法有时找到的解离最优解相差很远。
2) 两阶段法
通过对构造算法的研究,认为由构造算法求得的解可以被进一步,改进,为此学者们提出了两阶段法。第一阶段是得到一个可行解,第二阶段通过对可行解的调整,在始终保持可行解的情况下,力图向最优目标靠近,每步都产生另一个可行解以代替原来的解,使目标函数值得以改进,一直继续到不能再改进目标函数值为止。一直继续到不能再改进目标函数时为止。如Gillett和Mille的Sweep算法,,Renaud等的Prtal算法,,。
两阶段法求解过程中,常常采用交互式优化技术,把人的主观能动作用结合到问题的求解过程中,其主要思想是有经验的决策者具有对结果和参数的某种判断能力,并且根据知识直感,把主观的估计加到优化模型中去。这样做通常会增加模型最终实现并被采用的可能性。两阶段法是目前成果最丰富、应用最多的一类方法。每一种方法讨论的情况不尽一致,使用范围也不完全相同。
3)亚启发式算法
亚启发式算法一般从初始解开始,通过对当前解不断进行局部扰动以达到较好的
解。常见的有模拟退火算法(Simulated Annealing,SA)、神经元网络伽,(Neural Networks,NN)、禁忌搜索算法曲(Tabu Search,TS)、遗传算法(Genetic Algorithms,GA),、蚁群算法(Ant Algorithms,AA)。
模拟退火算法是1983年由Kirkpatrick等人首次提出的随机性搜索方法。模拟退火算法的基本思想就是用物质系统的退火过程来模拟优化问题的寻优过程,当物质系统达到最小能量状态时,优化问题的目标函数也相应地达到全局最优值。模拟退火算法在搜索策略上与传统的随机搜索方法不同,它不仅引入了适当的随机因素,而且还引入了物质系统退火过程的自然机理。近年来,模拟退火算法被应用于求解物流配送车辆调度问题,取得了一些研究成果。但多限于对无时限单向物流配送车辆调度问题或满载物流配送车辆调度问题的求解。
人工神经元网络的研究始于1943年,它是由心理学家W.S.McCulloch和数学家W.Pitts所提出的一模型。人工神经元网络是生理学上的真实人脑神经网络的结构和原理,以及若干基本特性的某种理论抽象、简化和模拟而构成的一种信息处理系统。该算法利用神经网络中神经元的防同并行计算能力来构造的优化算法,它将实际问题的优化解与神经网络的稳定状态相对应,把对实际问题的优化过程映射为神经网络系统的演化过程.
蚁群优化算法是受到自然界的蚁群觅食行为的启发而提出的,是一种用于求解组合优化问题的新型仿生进化算法,该算法首先由意大利学者M.Dorigo等人提出,最初的蚁群优化算法称之为蚁群系统,。蚁群优化算法在许多相当困难的组合优化问题的求解中体现了极强的寻优能力和较好的性质。
遗传算法是模拟生物在自然环境中的进化过程而形成的一种自适应、全局优化概率搜索方法。遗传算法的概念最早是由Baglay.J.D在年提出来的。经过近30多年的不懈努力,遗传算法不仅己经发展成为解决复杂全局优化问题的重要方法,而且在很多研究领域的具体科学实践中得到广泛的应用并获得成功。与其他算法如梯度下降法相比,遗传算法在优化求解时不易落入局部最优且具有很高的搜索效率。

第三章 案例背景与问题的分析
3.1 案例背景介绍
问题以泉峰公司运输汽车部件为背景,属于封闭式路线规划问题。南京泉峰公司在有关汽车零部件方面几乎是每天都要对几个公司进行配送。(出发地均为南京市).目前使用一种货车,其货箱尺寸如下:
【货车货箱尺寸】

【客户、产品名称和配送要求】

【客户地图和对应编码】
数字1,2……8分别对应南京,江苏太仓,舍弗勒上海,西门子上海,江苏徐州,江苏镇江,江苏苏州,安徽滁州。

【行驶里程表】

3.2 问题的提出
整个运输过程为:车辆从南京出发,经过需要配送的地区,最终返回南京。在运输过程中,只有前往的车辆有负荷,返回的车辆认为是零负荷。关于运输费用部分,我们可以大致分为有负荷时的运输单价、没有负荷时的运输单价和使用每辆车辆的固定费用。根据网上查询资料,我们达到三种费用的大致比例为 1:1.2:3 。
(1) 根据上述条件,求出总费用最少的运输路径
(2) 求所用车辆最少的方案。
建立基本假设如下:
① 每个客户仅由一辆车一次完成服务
② 假设所有的服务都能在规定时间内到达
③ 假设车辆在返回途中为零负荷
④ 假设运输中遭遇的堵车极少,且对运输费用的影响记为零
3.3 问题的分析
1. 需要解决的问题
这是一个典型的VRP问题,融合最小树和旅行商问题。按照题意,需要解决的问题是拿出一个优化的车辆路径规划方案,包括派多少辆车,每辆车上装载多少货物,安排走哪条路线。
2. 达到的目标
根据选择不同,有两个目标:
(1)求总运输费用最少
(2)使用的车辆数最少
3. 约束条件分析
(1)每个客户仅由一辆车一次完成服务。
对此,特别引入变量,它标志着是否有车辆k从客户i直接达到客户j,如果有,则取值1,反之则取值0。
(2)车辆重量限制。
为了避免出现超载等问题,我们对商品的重量进行限制,由于在运输过程中存在多种商品,我们首先计算每个需求点的总重量,即商家需求的数量*对应的单位重量。
(3) 在建模过程中,我们对于每条路径客户间的容量进行约束。
a. 车辆数量限制
泉峰配送中心可以使用的车辆数有限,因此在安排时需要限制总的车辆使用数。
b. 车辆运输费用要求最低
为了方便计算,我们将有负荷时的运输单价、无负荷时的运输单价与城市之间的距离进行运算,求出城市之间每条路径的运输可变费用。
c. 整数约束
决策变量是非负整数。
第四章 数学模型及其应用
4.1 以“总运输费用最少”为目标

1.建立符号体系
V为客户集合,客户数量为n=|V|;
0为配送中心;V0=VU{0} ;
cij为客户i和J之间的运输费用(城市i和j之间的距离*相应的运输单价);
pi为客户j的取货量,dj为客户j的送货量,j=1,2, . . .n;
Q为车辆容量;K为配送中心最大车辆数目;
xijk=1,车辆k从客户i直接达到客户j;
xijk =0,车辆k没有从客户i直接达到客户;
yij为途经弧( i, j)的i之前(包含i)的客户取货总量;
Zij为途经弧(i, j)的i之后的客户送货总量;
S为每辆车的固定费用;
2.根据实际问题调整模型

在上述表达式中,约束条件是总的运输费用最低。约束条件(3.1)说明每个客户仅由一辆车一次完成服务;约束条件(3.2)说明对每个客户达到和离开它的车辆相同;约束(3.3)说明最多只能使用K辆车;等式(3.5)和(3.6)为客户的取货量和送货量表达式;约束(3.7)为每条路径客户间的容量约束;约束(3.8)是每辆车的行驶距离约束,L是每辆车的最大行驶距离;约束(3.9)为决策变量属性。
3.求解过程
Global optimal solution found.
Objective value: 2949.200
Objective bound: 2949.200
Infeasibilities: 0.000000
Extended solver steps: 0
Total solver iterations: 7
最终求得的路径为:
1到6到7,返回
1到3,返回
1到4,返回
1到2,返回
1到8,返回
1到5,返回

4.最终结论
返回路线:西门子上海到南京,江苏徐州到南京,江苏太仓到南京,舍弗勒上海到南京,江苏苏州到南京,安徽滁州到南京。
最终使用6辆车。

4.2以“所用车辆数量最少”为目标

最少使用的车辆数为6辆,与问题(1)所用车辆数数目相同,可见问题二的最优解不唯一,至少有两个。
问题(1)和问题(2)结合起来,使用车辆数最少,且运输总成本最低的方案是1到6到7,返回;1到3,返回;1到4,返回;1到2,返回;1到8,返回;1到5,返回。
第五章 问题的总结与展望
5.1 涉及因素
首先是考虑的因素更加贴近实际情况,不仅考虑了有无负荷时的运输单价和每辆车的固定费用等多种运输费用,而且还考虑多种商品的体积重量限制,同时增加堵车概率,往返同时运输货物等安排。
5.2 运算时间
该模型涉及59个变量,66个约束条件,303个非零变量,而运算时间不足1s,因此从总体上看,用lingo求解既没有遗传算法、粒子算法等启发式算法复杂,而且运算时间几乎为零,掌握起来也方便容易,占有优势地位。对于NP问题,各种启发式算法都不可避免的遭遇到局部最优的问题,且迭代次数多比较多。根据网上查阅MATLAB运算遗传算法,迭代次数为900次时,运行时间是10s。这远远大于lingo求解的时间。
5.3 建立的模型
最终建立的模型只有9个约束条件,就可以解决VRP问题。车辆路径问题是一个典型的组合优化问题,是一个 NP 难题,一般情况是使用启发式算法,但是启发式算法中的参数对算法的效果起着至关重要的作用,如何有效设置参数至关重要,这对于模型的收敛性以及运算时间影响都很大。严重时,当.启发算法缺乏有效的迭代将停止条件。
5.4 解的精确性
启发式算法得到的解只是近似最优解,这与启发式算法的本质有关。而lingo求解相对来说能快速得到精确解。
5.5 问题的展望
1. 对于大型配送中心需要不定时运送多种商品时,需要考虑时间窗,惩罚金等。
2. 在考虑限制条件时不仅考虑重量,也可以考虑体积等因素。
3. 对于运输不同的物品,运输要求不一样,例如生鲜产品,由于保鲜时间短的特质就需要选择耗时短且道路平稳的路径。
4. 对于堵车问题,不仅可以从整体的堵车情况考虑,还可以对具体路段做要求。
5. 在考虑客户需求时可以引入相似的数据进行模拟、预测,便于安排具体的路径。
6. 当然仍然可以在此基础上选择车辆的型号,租用还是购买等事项。
7. 在运算上,对于模型最优解不唯一的情况下,使用lingo求解只能求出一种方案来,是需要进一步解决的问题。

发表评论

:?: :razz: :sad: :evil: :!: :smile: :oops: :grin: :eek: :shock: :???: :cool: :lol: :mad: :twisted: :roll: :wink: :idea: :arrow: :neutral: :cry: :mrgreen: