摘 要

成品油二次配送是指成品油从大型油库到各地加油站的配送过程，在二次配送过程中，由于车辆调度和物资分配不合理，造成了极大的资源浪费，从而导致物流成本过高。随着成品油市场竞争日益激烈，针对二次配送过程的路径优化不仅能提高企业竞争力，同时还能给客户提供更优质高效的配送服务。借助真实有效的数学模型和科学的算法优化，可设计出合理的资源调度方案，实现资源利用的最大化，大幅减少配送成本。

本文针对此问题，首先总结了成品油二次配送过程的影响因素，通过分析带时间窗的车辆路径问题的基本原理，对比了求解该问题的各种优化算法的优劣点，最后选用了列队竞争算法，该算法实现较为简单，同时具有高效的搜索能力，优化能力强。在考虑配送中心、运输网络和客户三者的约束条件下，建立了带时间窗的车辆路径优化模型，同时针对此模型设计了切实可行的列队竞争算法。最后通过算例测试，验证了在该模型下算法的有效性，并选取了武汉二十五个加油站作为实例，调用百度地图API获取实时路况，模拟了基于实时路况下的成品油二次配送的路径优化过程，分析不同路况下的优化结果。

关键词：成品油二次配送、时间窗、车辆路径问题、列队竞争算法、实时路况

Abstract

The secondary distribution of refined oil refers to the distribution process of refined oil from large oil depots to gas stations in various places. In the process of secondary distribution, due to unreasonable vehicle scheduling and resource allocation, great resource waste is caused, resulting in high logistics cost. With the increasingly fierce competition in the refined oil market, the route optimization for the secondary distribution process can not only improve the competitiveness of the enterprise, but also provide customers with better and more efficient delivery services. With the help of real and effective mathematical models and scientific algorithm optimization, a reasonable resource scheduling scheme can be designed to maximize resource utilization and reduce distribution costs.

In order to solve this problem, this paper first summarizes the influencing factors of the secondary distribution process of refined oil. By analyzing the basic principle of the vehicle routing problem with time window, the advantages and disadvantages of various optimization algorithms for solving the problem are compared. Finally, the queue is selected. The competition algorithm is simple to implement, and has efficient search ability and strong optimization ability. Under the constraints of distribution center, transportation network and customers, the vehicle path optimization model with time window is established. At the same time, a feasible queue competition algorithm is designed for this model. Finally, through the example test, the effectiveness of the algorithm is verified. The twenty-five gas stations in Wuhan are selected as examples. The Baidu map API is used to obtain real-time road conditions, which simulates the path of secondary distribution of refined oil under real conditions, analyzing the optimization results under different road conditions.

Keywords: secondary distribution of refined oil, time window, vehicle routing problem, line-up competition algorithm, real-time traffic

目录

摘要 I

Abstract II

第1章 绪论 1

1.1 研究背景及意义 1

1.2 国内外研究现状 1

1.2.1国外研究现状 2

1.2.2国内研究现状 2

1.3 研究方法及内容 3

第2章 成品油二次配送问题 4

2.1 成品油二次配送问题概述 4

2.1.1约束因素 4

2.1.2目标函数 5

2.2 车辆路径问题求解算法 6

2.2.1精确算法 6

2.2.2启发式算法 7

2.3 列队竞争算法 8

2.3 本章小结 10

第3章 模型构建和算法设计 11

3.1 模型构建 11

3.1.1问题描述 11

3.1.2基本假设 12

3.1.3参数说明 12

3.1.4目标函数及约束条件 13

3.2 列队竞争算法设计 14

3.2.1个体编码 14

3.2.2种群初始化 14

3.2.3适应度函数 15

3.2.4进化变异 15

3.2.5终止进化 15

3.3 百度地图API调用 16

3.4 本章小结 16

第4章 算例分析 17

4.1 R101数据测试 17

4.2 基于武汉加油站的实例测试 19

4.3 本章小结 21

第5章 总结 22

参考文献 23

致谢 25

第1章 绪论

1.1 研究背景及意义

成品油是原油经过加工提炼得到的产品，是重要的能源物资，随着世界经济的发展，成品油的需求量也在日益上升，其作为世界经济的重要驱动力之一，在世界经济体系中的重要性不言而喻。2018年一月至十月，我国成品油的产量达30365万吨，同比增长7.0%。在成品油市场需求越来越高的同时，成品油市场的竞争也愈渐激烈，国家多次出台成品油行业的相关政策，制定了一系列的维护成品油市场稳定的措施，旨在完善成品油价格机制。受到经济全球化的影响，国内成品油也与错综复杂的国际市场接轨，在考虑企业的生产成本和消费者的经济能力的同时，还要考虑国际成品油市场竞争，价格机制的建立和完善面临许多干扰因素的挑战。在这种情况下，我们需要找到新的突破口提高国内成品油企业的竞争力，使其在国际的成品油市场中占有一席之地，同时也对维护国内成品油市场的稳定有着重要帮助。

相较于国外的成品油企业，我国在成品油物流方面的成本普遍过高，成品油的物流成本是其生产总成本的重要组成部分，特别是对于中石化、中石油这样的大石油公司，其运输调度的管理至关重要，市场配置往往决定了整个产品的销售利润，也决定了成品油在市场中的销售价格。在成品油的二次配送中，由于设备布局不合理、库存管理不集中、管理信息不统一等原因，使得二次配送在资源上造成了许多不必要的浪费。因此，摆脱传统配送管理所带来的资源浪费，提高配送中心的共享信息化管理，利用高效的数学模型来完成科学的配送规划，可以大幅度减小企业在物流成本的浪费，提升企业竞争力，因此成品油二次配送问题具有相当重要且现实的研究意义。

1.2 国内外研究现状

成品油的二次配送是其物流过程中的重要一环，作为物流系统的组成部分，我们可将该问题描述为车辆路径问题。车辆路径问题（VRP）和著名的旅行商问题（TSP）类似，通过路径选择以达到节省时间或成本的目的，但车辆路径问题要考虑更多的约束条件，在实际场景下的应用更多，受到许多研究者的关注。自车辆路径问题被提出以来，关于求解该问题的算法可分为三个阶段，第一阶段是精确算法，第二阶段是传统的启发式算法，而第三阶段则是我们正处在的阶段，主要是现代启发式算法和人工神经网络等。

1.2.1国外研究现状

国外的学者对于车辆路径问题的研究较早，自该问题被提出以来，相关研究者针对该问题建立不同的数学建模，同时也提出了不同的优化求解算法。

Osman^[1]等于1993年提出了基于混合模拟退火和禁忌搜索算法的近似方法，并研究了不同的搜索策略，采用了一种特殊的数据结构使其能更快的解决问题。

Christian Prins^[2]于2004年提出了一种更简单有效的遗传算法，解决了车辆路径中遇到的硬组合优化问题。

Bin Yu^[3]等于2009年基于蚁群算法做了一些改进，时期具有更新增加的信息素的新策略，称为蚁群权重策略和变异操作，以解决信息更新的问题。

Xiangyong Li^[4]等于2010年研究了一种配送和服务时间是随机的模型，并且时间窗口约束与每个客户相关联。该问题最初被表述为机会约束编程模型和随机编程模型，为了有效地解决这两个模型，提出了一种基于禁忌搜索的启发式算法，该启发式算法考虑了该问题的随机性。

Andrei Horvat Marc^[5]等于2012年提出了一种广义的车辆路径问题（GVRP），GVRP是设计从给定的仓库到多个预定义的，互斥的节点集（集群）的最佳交付路线问题，同时针对此问题提供了两种基于整数规划的新模型。

M.B.Guzairov^[6]于2017年总结了经典车辆路径问题的数学模型，带时间窗的车辆路径问题，以及车辆路径问题的分类，同时考虑了运输路线的不同方面，提出了具有时间窗的多配送中心车辆路径问题的解决方案的数学模型和方法。

1.2.2国内研究现状

国内对于车辆路径问题的研究起步较晚，但随着物流技术的发达，客户对配送服务要求的提高，国内研究者在现有的算法上提出了很多创新的理论和组合优化的方案。

周贤伟和李远光^[7]于2001年基于具有时间窗的车辆路径问题，通过车载GPS获取车辆的位置信息，并从位置信息提取可靠的数据来建立数学模型，最后设计了求解该问题的遗传算法。根据真实可靠的数据以及科学的算法来解决此问题，使得该研究的实际应用性强。

张丽萍^[8]等人于2002年提出了一种改进的遗传算法，使得算法的全局搜索能力变强，具体的做法是改变算法中的遗传算子，解决了遗传算法中在局部最优点收敛的问题。

蒋文霞^[9]于2007年将模拟退火算法和邻域搜索算法进行结合，这样不仅保证解空间的多样性，还优化了搜索过程中得到问题新解的选择机制，最后可快速收敛到解空间中的最优解。

黄务兰和张涛^[10]于2016年提出了一种改进的遗传算法IGALS，改进算法的选择机制，防止丢弃优秀的个体，采用点交叉和段交叉算子结合的交叉算子，并以此为依据使用局部搜索策略进一步提高解的质量。

陈呈频^[11]等人于2018年证明了多染色体的遗传算法在求解多车场多车型车辆路径问题时,不仅呈现出搜索效率高和收敛速度快的特点,而且解的质量和稳定性高。

1.3 研究方法及内容

本文从成品油二次配送问题入手，结合实际运输过程中的约束条件，总结了成品油二次配送中造成物流成本过高的原因，以降低配送成本为目标，建立了此问题的数学模型，并为模型求解设计可行的列队竞争算法，通过算例测试验证算法的合理性，最后解决实际成品油二次配送的路径优化问题。论文的研究可分为四个部分：

1）第一部分：介绍问题的提出背景和研究现状。第一章介绍了本文的研究背景和意义，以及国内外在该领域的研究现状和论文具体的研究方法及内容，为本文研究的方向提供指导和参考。

2）第二部分：分析问题的要素，探讨解决问题的思路。第二章和第三章概述了成品油二次配送问题的要素和目标，总结车辆路径问题的求解方法，并分析探讨了各方法的核心思想以及优劣点，给模型建立和算法设计提供依据。

3）第三部分：设计解决问题的方法，用算例证明方法的合理性和有效性。第四章和第五章首先根据带时间窗的车辆路径问题建立数学模型，并设计了实际可行的算法，最后用算例的结果分析算法的正确合理性。

4）第四部分：总结解决问题的过程，阐述本文研究的成果及意义。第六章对本文的研究工作做了总结，系统阐述了本文研究取得的实践性成果。

第2章 成品油二次配送问题

2.1 成品油二次配送问题概述

成品油的配送过程是指成品油供应商指根据各地的市场需求，将成品油从供应地运输到加油站或消费用户的运输过程。成品油的物流运输一般可分为一次配送和二次配送，其中从大型炼油厂通过公路运输、铁路运输、管道运输等运输方式，运输到各地的销售企业油库的配送过程称为一次配送，从油库以公路车辆运输为主要运输方式运输到加油站或客户的配送过程称为二次配送。本文的研究对象是成品油二次配送过程，由于车辆调度和路径选择不合理造成了极大资源浪费，这也是物流成本过高的直接原因，物流成本不仅包括物资成本，同样也包括人力成本以及时间成本，通过路径优化可以使资源利用最大化，同时也减少了人力和时间的投入。路径优化是指在考虑到配送中心（油库）的车辆调度、各个客户（加油站）的服务时间窗和油量需求、以及运输网络等因素下，制定合理的配送车辆运输方案，使得每辆车的载重能充分利用，每个客户能得到及时优质的服务，最后满足我们的预定目标。

成品油二次配送问题可描述如下：一个配送中心需要给m个客户完成配送任务，有且只有一个点能给其他点提供配送服务，即配送中心，m个客户都有需求，每个客户都需要被服务。配送中心的车辆有同样的载重量Q，同时车辆发车收车有时间限制，每个客户有各自的需求量q，同时还有服务时间窗限制。我们可以发现成品油二次配送问题就是典型车辆路径问题，在众多约束条件下求目标函数的最优化值。

2.1.1约束因素

成品油二次配送在实际的配送情境下需要考虑许多约束因素，主要包括配送中心的配送约束，客户的需求量以及服务时间约束。

1. 配送中心的约束因素

配送中心（油库）的约束因素主要包括配送车辆的数量、车辆载重以及收发车的时间。配送中心在制定配送方案时不仅要考虑客户的需求，同时还要考虑该配送中心的物资储备，如车辆数量，发车时间以及车辆载重。如果车辆数量充足，即不考虑车辆数的限制，在这种情况下每次配送的车辆调度可同时进行，可以节省大量的时间，最大程度满足客户的服务，本文就是建立在这种假设上的。

当一辆车的载油量不能满足下一客户的需求时，会返回至配送中心由下一辆车完成剩下客户的服务。另外，由于配送中心还需规定发车和收车时间，即配送车辆要在规定时间内完成配送并返回配送中心，如果配送车辆在完成一个客户的服务后无法按时返回配送中心，则会放弃给该客户服务由下一辆车完成该客户的服务。

1. 运输网络的约束因素

运输网络的约束因素主要包括距离和路况。运输网络是指配送过程中车辆的行驶路线，在真实情况下，车辆会选择距离最短或耗时最短的路径，从而节省时间。由于各地的交通路况不同，所以很难做统一的判断标准，即使同一地点的交通路况也会随着时间变化，比如早高峰晚高峰的实时路况肯定与其他时间的路况是不同的。在这种情景下，基于实时路况的车辆运输问题更具有挑战性和真实性。成品油的二次配送是发生在油库和加油站之间的运输过程，市区内加油站大多在交通繁忙的街道，所以这是一个不确定的影响因素。基于过往经验的判断在多数情况是有效的，但面对不可知的交通状况，经验能发挥的作用有限，只有准确的获取两点之间的行驶时间，路径规划的正确性和实用性才能体现。

1. 客户的约束因素

客户（加油站）的约束因素主要包括油量需求和服务时间窗。不仅要根据先前的销售记录确定自己的需求量，同时还需要考虑服务时间窗，保证每天的销售任务能正常进行。

在车辆路径问题中，时间窗可分为硬时间窗和软时间窗两种，硬时间窗是指客户只在规定时间窗内接受服务，早到需要等待至最早开始服务时间，晚到则拒绝服务；软时间窗是指在时间窗外早到和晚到仍可以接受服务，但都需要接受惩罚，惩罚值为定义好的惩罚因子乘以时间。

假设一个客户的需求量为20，服务时间窗为早上6.00至6.30，则配送车辆为该客户服务时的载油量应大于20，同时应在服务时间窗内到达， 如果早于6.00或晚于6.30则会受到惩罚（软时间窗）。

2.1.2目标函数

目标函数是指问题的最终目标，车辆路径问题中的目标函数主要有：配送成本最小、配送距离最短、最大限度满足时间窗等。

1. 配送成本最小，成本不仅包括配送距离的成本，同时还包括车辆成本以及上一节提到的软时间窗惩罚成本，其中车辆成本是基于车辆数量的成本--每辆车的成本×车辆数量，距离成本是基于距离的成本--每千米的成本×路径距离，惩罚成本是基于时间的成本--每分钟的成本×早到或晚到时间，早到和晚到的惩罚因子可以不一样。

2. 配送距离最短，配送距离是指完成整个配送任务所有车辆行驶路程的总和，要使距离最短，即要求在约束条件下找到最优的配送顺序，尽量避免车辆大范围移动，需要考虑客户的分散情况。