物流工程硕士论文：时间依赖性路径问题及算法研究

　　
　　随着城市交通拥堵日益加剧，企业配送成本高居不下，同时，客户对企业配送效率要求不断提高。为此，一个科学的配送方案对物流企业来说尤为重要。由于受交通流量和交通事故等影响，道路通行时间是动态变化的，不同出发时刻产生的配送时间和配送成本不尽相同。因此，深入时间依赖性车辆路径问题（TDVRP）有着重要的理论意义和现实价值。文章旨在利用道路通行时间连续函数构建TDVRP模型，并通过求解该模型，为企业提供一个包含配送路线、最佳出发时刻，兼顾成本和满意度的科学解决方案。主要从以下方面进行了研究：
　　
　　分析与改进了TDVRP模型中通行时间函数，建立连续时间函数模型。综合分析三种时间数据的获取方案后，选用地图软件作为本文基础数据获取途径。根据路段通行数据的规律，利用高斯混合理论，应用Matlab构建实际路网的道路通行时间函数。结合实际数据，与分段时间函数进行对比，结果表明连续函数能更为准确地反映出发时刻与道路通行时间的关系。
　　
　　利用道路通行时间函数构建单目标、多目标TDVRP模型。前者是以最小化成本为目标函数，寻找成本最低时的配送路线和最佳出发时刻。后者以客户时间窗为基础构建了客户满意度函数，建立以最小化配送成本和最大化客户平均满意度为目标函数的模型，寻找兼顾成本和客户满意度的配送路线和最佳出发时刻。
　　
　　针对模型特点，设计两阶段求解算法。第一阶段，以配送中心与客户之间的最短路径为权值，利用Dijkstra算法求解出配送中心到各客户的最短距离，并在考虑约束条件下，规划配送路线。第二阶段，利用遗传算法分别计算出每条路径的最佳出发时刻和对应成本。在对多目标求解时，先求得满足要求的客户满意度区间，以此区间作为遗传算法自变量的上下限，再计算最低成本下的最佳出发时刻。实际案例的分析结果表明：模型符合实际，具有普适性。通过分析道路的通行时间，规划配送路线，选择一个最佳的出发时刻进行配送，能够降低企业配送成本、提高客户满意度。
　　
　　关键词：  道路通行时间函数；TDVRP；配送路径；最佳出发时刻；客户满意度。
　　 　　
　　As traffic jams in the city get worse, enterprises's delivery cost keeps high. At the same time,  customers  have  more  desire  for  improve  delivery  efficiency.  Therefore,  a  scientific distribution  plan  is  especially  important  for  logistics  enterprises.  Due  to  traffic  flow  and traffic  accidents,  road  traffic  time  is  dynamic,  and  different  departure  times  have  different delivery  time  and  delivery  cost.  Therefore,  it  is  of  great  theoretical  and  practical  value  to deeply  study  the  time-dependent  vehicle  routing  problem  (TDVRP).  The  article  aims  to build  TDVRP  models  using  road  continuous  transit  time  functions  and  solve  the  model  to provide enterprises with a scientific solution that includes delivery routes, optimal departure times,  taking  into  consideration  cost  and  customer  satisfaction.  It  mainly  includes  the following four aspects:
　　
　　The article analyzed and improved the road transit time function in the TDVRP model and  established  a  continuous  time  function  model.  After  comprehensively  analyzing  the acquisition schemes of the three kinds of time data, we used map software as the basic data acquisition  method  for  this  article.  According  to  the  rules  of  road  traffic  data,  the  Gauss mixture  theory  was  used  to  construct  the  road  network  time  function  of  the  actual  road network by Matlab. Combined with the actual data,. the results showed that the continuous function  could  more  accurately  reflect  the  relationship  of  departure  time  and  travel  time than the piecewise time function.
　　
　　The  road  transit  time  function  was  used  to  build  single-objective,  multi-objective TDVRP model. The former was used the minimization cost as the objective function to find the delivery route and the best departure time when the cost was the lowest. The latter was built a customer satisfaction function based on the client's time window, established a model that minimizes delivery cost and maximize customer satisfaction as the objective functions, and looked for delivery routes and optimal departure times that took into account both cost and customer satisfaction.
　　
　　Aiming  at  the  characteristics  of  models,  we  designed  a  two-stage  algorithm  to  solve this function. In the first stage, taking the shortest path between the distribution center and  the customer as the weight value, Dijkstra algorithm was used to find the shortest distance between  distribution  centers  and  customers.  And  we  planned  distribution  route  under  the consideration of constraints. In the second stage, the genetic algorithm was used to calculate the  optimal  departure  time  and  cost  for  each  path.  In  the  case  of  multi-objective  solution, the customer satisfaction interval that satisfies the requirements was first obtained, and this interval  was  used  as  the  upper  and  lower  limit  of  the  genetic  algorithm's  independent variable, and then the optimal starting time of the lowest cost was calculated.The actual case analysis showed that the model was practical and universal. By analyzing road transit times, planning  delivery  routes,  and  choosing  an  optimal  departure  time  for  delivery,  it  reduced corporate delivery costs and improved customer satisfaction.
　　
　　Keywords:    Road  transit  time  function;  TDVRP;  Delivery  route;  Optimal  departure  time; Customer satisfaction 。
　　 　　
　　1.1  研究背景。
　　
　　对社会经济发展而言，城市配送在经济发展、民生保障和环境保护方面有着重要影响。2017年，我国交通运输、仓储和邮政业增加值占GDP的比值为4.4%，为城镇提供4.7%的就业岗位。另一方面，近几年来，随着我国城市化进程的加快，2017年末城镇化率已经达到58.52%，城镇就业人口约占总就业人口的54.69%。就环境而言，运输过程中产生的尾气使得该行业成为温室气体排放的主要行业。据统计，全球二氧化碳排放有25%来自交通运输业，其中道路货运占比高达61%[1]。综上，城市配送和城市运输直接影响到城市的生产、居民生活需求能否得到及时高效的满足，是城市的经济和居民生活水平的重要支点。
　　
　　对城市而言，日益拥堵的交通问题成为大城市的通病，城市配送受到影响。随着经济的发展和人们收入水平的提高，汽车的数量迅猛增长，2016年私家车拥有量增速高达22.6%，使得城市拥堵问题日渐显露。另一方面，由于缺乏科学合理的配送设施规划，存在配送网路重叠、配送效率低下等问题，使本就交通紧张的城市变得更加拥挤。由此带来了能源消耗、城市污染等问题，同时还降低了居民的正常生活效率与质量。城市配送的核心在于车辆路径问题（Vehicle Routing Problem, VRP）[2]，有研究表明，合理规划配送路线能够节约5%-30%的费用[3]。研究城市配送的VRP问题，提高车辆的利用率，能一定程度缓解城市交通拥堵问题和环境污染问题。
　　
　　对配送企业而言，城市配送面临着巨大的挑战。据统计数据显示，运输费用占物流总费用的50%以上，而其中油费占运输费用的60%以上。国内油价的升高，土地成本以及人力等成本不断攀升，使得配送企业成本高居不下。随着同行竞争加剧，迫使配送企业寻找新的出路，降低配送成本。配送企业的现实诉求也促使学者对配送路径问题的研究，合理规划配送路径，制定科学的配送方案能在不增加成本的基础上实现配送成本的降低，提高配送效率和客户满意度。
　　
　　对客户而言，客户对城市配送有着更高的期望。由于现代商业模式的变革，客户至上的观念受到企业重视，小批量、多品种、多样化、个性化的配送需求不断增加[4]。随着人们生活质量的提升，客户对物流配送时效性、便捷性等提出了更高的要求。优化企业的配送路径，灵活选择配送车辆出发时刻能够提高客户的满意度，提高配送效率，增加企业效益。
　　
　　综合以上分析，研究城市配送路径规划问题，不仅能降低企业配送成本，提高配送效率，使企业实现配送成本和服务质量的双赢；还能够节约社会成本，缓解城市拥堵，改善城市环境；而且，从整个物流行业来看，配送路径的规划也利于节约物流总费用，促进物流行业整体的发展。
　　
　　1.2  研究现状。
　　
　　1.2.1  城市配送路径研究现状。
　　
　　城市配送路径问题作为国内外共同关注的热点问题，学者主要从两个维度——静态与动态、确定与随机，对VRP问题进行研究[5]。其中静态VRP问题是指在规划路径时，所有的输入信息，包括客户的需求以及路段的通行时间等，不会随着时间的变化而变化，相反则为动态。而确定性VRP问题是指所有的输入信息，包括客户的需求量以及路段的通行时间等都是提前已知的，相反则为随机[6]。而这两组相对维度又可进行交叉组合，形成静态确定VRP问题、静态随机VRP问题、动态确定VRP问题、动态随机VRP问题。
　　
　　静态确定性VRP问题是目前发展较为成熟的一类。比较有代表性的是容量限制的VRP问题（capacitated vehicle routing problem, CVRP）[7]，具体是指在路径规划之前，所有的输入信息已知，而不考虑道路通行时间随时间变化，但有容量限制。随着大城市交通拥堵问题的日渐显露，有学者开始对交通管制情境下的城市配送问题进行研究。胡云超[8]将限行时段转化为时间窗，得出交通管制会影响配送的效率和连贯性的结论，提出夜间配送的观点；赖平仲等[9]构建城市配送交通管制下的配送优化模型，并改进了遗传算法。电子商务的繁荣，在城市配送中不仅需要考虑送货路径，还要考虑取货的车辆路径问题。阮清方[10]提出一种新装卸策略的带取送车辆路径优化问题，从车辆车型、问题规模和算法等方面进行了研究论证。
　　
　　与静态确定性VRP相对的是静态随机VRP问题，在路径规划之前，存在不确定信息，比如需求量。崔丽等[11]提出了不考虑交通拥堵的情况下，建立由客户随机需求驱动下的城市配送车辆模型，将客户订单进行分类分组再进行聚类分析，再根据订单进行配送。朱佳翔等[12]针对生鲜农产品市场需求不确定的特点，构建了多目标的模糊决策模型，将不确定信息用模糊变量表示，并以实际案例验证和分析了模型。Lee等[13]采用鲁棒优化方法解决了需求的不确定的问题。这类问题求解思路主要是：将不确定信息以概率等形式转化为确定信息[14]。
　　
　　本文所研究的TDVRP问题（Time Dependent Vehicle Routing Problem, TDVRP）本质上是属于动态VRP问题。其数学模型最初由Malandraki[15]给出，提出之后得到了学术界的广泛关注，取得了不少研究成果。如Fleischmann[16]建立了尊重FIFO原则的TDVRP问题模型、Slater[17]等人利用浮动车辆数据构建了TDVRP问题模型等。
　　
　　最近几年，随着信息技术的进步，人们对智能交通系统的需求增强，时间依赖性旅行时间变得越来越重要。Ding[18]提出利用智能交通系统的实时交通信息以解决时间依赖的旅行时间。Duygu等[19]利用历史交通数据，采用了一种模拟方法估计交通拥堵和旅行时间。在求解方面，Kok[20]利用有限的动态规划启发式算法求解出具有时间相关最短路径的TDVRP，并证明了在TDVRP中利用时间相关最短路径的时间显着减少。同年，Ehmke[21]也在城市物流案例研究中，详细分析了TDVRP解决方案的时空结构。随机动态VRP问题通常是需求量、客户随机和动态时间相结合，是这四类问题最复杂的，研究相对较少。郭耀煌[22]针对这一问题，设定需求量服从泊松分布，当需求量是密集时，计算出期望时间的下限，旅行时间函数是关于某一时间为同一值的分段函数。此条件下，最终求得最小化配送时间。Chen[23]建立基于旅行时间变化的混合整数规划的模型，并利用启发式算法求解，效果良好。
　　
　　从以上研究可以看出，目前对城市配送路径问题研究较为充分，但更加符合现实情况的动态VRP问题还需要进行深入研究。主要表现为已有的动态性研究主要是客户的数量或需求量的动态变化，虽然有学者[24]研究了动态路网中的配送，但是其模型中时间函数是一个阶跃函数，需要处理跨时段的问题，计算复杂，且对实际的模拟能力有待提高。因此，需要构建一个更符合实际的道路通行时间，以此建立TDVRP模型。
　　
　　1.2.2  道路通行时间研究现状。
　　
　　TDVRP问题区别于其他的VRP问题，就在于车辆路径规划是依赖于道路通行时间。因此对道路通行时间函数的研究就成为TDVRP问题的重点。目前各国学者对旅行时间函数的处理主要有以下方法：
　　
　　此类问题研究的初期，许多学者将通行时间经过简单的处理后建立模型。Fisher[25]通过设定不同的权值来体现通行时间的变化。Brown[26]等在考虑TDVRP问题时，先求得一组静态配送路径，然后考虑高峰期的交通状况和交通事故等特殊原因，人为地对初始路径的配送顺序进行调整。这些研究一定程度上能模拟真实情况。
　　
　　Maden和Figliozzi[27]以15分钟为一时间段，观察道路的通行速度，综合超过3个月的实际流量数据，得出每日平均速度，以便为模型提供一个良好的近似解。另外，Kuo[28]、Jabali[29]和Franceschetti[30]等人的研究使用较少的速度水平来描述城市地区的典型交通状况。尽管Ehmke[31]和Qian[32]使用了更精细的速度水平描述24小时的交通状况，但是在他们的实例中，配送时间范围通常只包含一个高峰时段。
　　
　　在此基础上，许多学者[33][34][35]以高峰和平峰的通行速度，按时段对一天进行划分。在相同的节点上，不同时段的车辆行驶需要不同的时间，车辆的出发时间或者行驶速度被设定成一个阶段函数。在某一时间段，车辆通过节点的时间是固定的。Huang[36]假设配送时间窗[L，U]由R个时间段组成，并且在一个时间段内，在某一路段A的速度是恒定的行程速度。因此，路段A的行驶速度是在一天中是一个阶跃函数，路段A的相应行程时间函数是分段线性函数。对于一条路径，是由有限序列的道路分段组成，每一条路段都由一个连续分段的线性旅行时间函数组成。如图1-1和图1-2所示。
　　
　　有学者考虑将路网中的道路进行分类：快速路、主干道、次干道和街道，分别考虑各类道路的行驶速度，以此构建分段的道路通行时间函数[32]。实际上，同类道路在不同时刻的通行速度可能有着巨大差异，且同一条道路的不同时刻的通行时间也不尽相同。而且，在实际生活中，道路的通行时间函数不全是分段函数，而是随时间动态变化的平滑的连续性函数。构建一个包含一整天的工作时间的道路通行时间函数，对于指导配送有着重要作用。

······

结 论

　　随着经济的发展和人们收入水平的提高，汽车的数量迅猛增长，我国许多大城市交通拥堵现象日渐突出，与此同时，不论个人还是企业对时间成本的概念愈加重视，特别对物流企业来说制定科学的配送方案以减少配送时间和成本尤为重要。因此，在此背景下，本文应用高斯混合模型理论、运筹学和Matlab，对基于道路通行时间的城市配送路径规划进行了研究，主要研究结论如下：

　　1.应用高斯混合理论给出了道路通行时间连续函数构建方法，对该函数进行了改进，相比于以往的分段时间函数，连续函数能够更为准确地反映道路通行时间与出发时刻的关系。本文应用高斯混合理论，构建连续的道路通行时间函数，结合实际数据与分段时间函数进行对比，本文函数所算出的时间与实际到达时间的误差最高为13.6%，而分段函数计算出的误差高达77.1%，误差是本文的5倍多。

　　2.基于道路通行时间连续函数建立了具有时间依赖性配送路径规划TDVRP模型。相比传统的VRP问题，该模型不仅可以规划配送路线，还能得出最佳出发时刻。其中多目标的TDVRP模型以时间窗为基础建立客户满意度函数，该模型体现在末端配送中，配送企业规划路线不仅考虑配送成本，还会考虑客户满意度降低带来的客户流失，说明模型符合实际。

　　3.给出了一种TDVRP模型的两阶段求解方法。计算结果表明在考虑一个目标函数的前提下再求解另一个目标函数，能很好地兼顾两个目标，减小计算量。同时考虑客户满意度和配送成本比只考虑成本最小时的配送成本仅增加1.5%，配送时间仅增加1.9%，企业合理安排配送车辆出发时刻，能同时兼顾企业和客户的利益。

　　4.通过本文优化结果与企业通常配送出发时刻的求解结果相比，可以发现：合理改变配送出发时刻，能降低8%的配送成本，减少9.4%的配送时间，且使客户满意度均达到90%以上。结果表明，借助本文的研究成果，可以为物流企业制定一个更加科学的配送方案。