《硕士学位论文-基于路径优化和博弈论的物流配送定价方法研究.doc》由会员分享，可在线阅读，更多相关《硕士学位论文-基于路径优化和博弈论的物流配送定价方法研究.doc（83页珍藏版）》请在三一文库上搜索。
1、硕 士 学 位 论 文基于路径优化和博弈论的物流配送定价方法研究i目录摘要iiiABSTRACTiv第一章绪论11.1 研究背景和意义11.2 国内外研究现状51.2.1 车辆路径选择问题研究现状51.2.2 物流配送定价研究综述91.3 本文主要研究内容和技术路线10第二章相关理论基础132.1 车辆路径问题概述132.1.1 一般车辆路径问题的特征和目标132.1.2 车辆路径问题基本类型152.2 遗传算法概述172.2.1 遗传算法理论基础172.2.2 遗传算法的描述与设计202.3 博弈论概述29第三章去程单一目的地的路径优化和定价303.1 带返程配送问题的描述303.2 返程路
2、径及利润优化的数学模型313.3 求解的遗传算法设计323.4 返程利润及路径优化算例353.5 小结39第四章去程多目的地的路径优化和定价404.1 去程路径优化的数学描述404.2 求解的遗传算法设计414.3 去程路径优化算例424.4 来返程综合算例的结果与分析464.5 小结48第五章客户与承运者的博弈分析495.1 客户与承运者之间的博弈模型495.2 两个及多个承运者竞价的博弈模型525.3 小结55第六章结论与展望56参考文献59附录A64附录B73 第一章 绪论第一章绪论1.1 研究背景和意义近年来，我国物流业蓬勃发展，各类物流公司应运而生，外资物流公司也大举进入我国物流市场
3、。尤其是在中国入世三年后，配送市场完全开放，竞争更加激烈。由于大多数物流公司都提供公路干线配送服务，因此在这一领域的竞争尤为激烈。目前，公路干线配送已成为5种主要配送方式中完成配送量最多，实现营业收入最高的一种配送方式。2002年底，全国在运管部门登记注册的公路配送汽车达826.3万辆，其中载货汽车536.8万辆；2002年，全社会货运量为111.6亿吨，货运周转量为6782.5亿吨公里，并且全国的货运量及货运周转量都在逐年升高1。巨大的市场吸引了众多的服务提供商。然而，多数物流公司只能提供初级的服务，如配送和仓储。这些服务如此相似，使得配送市场几乎处于完全竞争状态，价格很低，物流公司几乎无利
4、可图。经过对省内一些物流公司的调查、了解，物流公司目前普遍面临着以下一些问题：（1）物流配送网络较小调研公司中配送网络的幅射面积不大，一般业务点都设在本市或本省的主要城市。省外业务网络分布范围不广，多数集中在沿海主要城市和内陆的大城市，网络覆盖面没有达到长三角更不用说全国。（2）仓储配送设施较落后仓库大多是普通平房，现代化仓库比例极低，具有冷藏、保鲜、气调功能的仓库更少；只有极少数公司拥有先进的仓储技术，能够利用JIT流程控制技术进行配送。搬运工具一般人工搬运车、手推叉车和普通起重设备较多，可视屏叉车等现代化的搬运工具却很少采用。在配送工具方面，普通货车占较多，集装箱车及特种配送车很少。调研中
5、多数物流公司都可以进行配送，但专门建立的配送中心不多。（3）信息处理水平还较低许多物流公司更关注于对实物流的控制，信息系统还只是货物配送的附属品，仅能做到对货物配送信息的计算机录入、存储和传输，但缺乏对信息的主动利用，数据的采集、统计分析预警能力还不够，与实物流、资金流的同步衔接能力差，很难形成面向客户的电子商务物流模式；对于智能配送系统也基本空白。通常只有危险品车辆才会被强制要求配备GPS。对于普通货物配送，大多数情况下是通过手机进行信息沟通的。（4）财力不足省内的物流公司正处于发展期中，本身的净收入就不高，加上历史的原因造成的负担过重，使利润率和利润都很低，公司很难依靠自有积累发展。虽然调
6、研中公司的总资产很高，但由于配送中需要押金和垫付大量现金，因此多数物流公司的现金流转很困难。由于物流行业的投资回报周期长，银行不愿意贷款，这使公司的发展更加困难。（5）营销与客户服务过于狭窄省内的一些物流公司由于规模不够大实力不够强，不得不依附于一两个大客户，这些客户成为公司的主要甚至可以说是唯一的利润源。一旦这几个客户丢失，公司就可能面临倒闭。因此物流公司将这些客户放在了至高无上的地位，愿意花费大量的成本来满足客户的需求。这使物流公司处于极其被动的地位，其发展的前景完全依赖于客户的发展，风险很高。（6）物流与供应链研究落后省内公司的规模不大实力不强，还没有专门进行物流与供应链管理研究的部门。
7、调研的公司多数还是以业务和利润为主导，把注意力放在联系客户和扩充市场上，客户走到哪里，网络就铺到哪里，客户需要什么公司就提供什么服务，一切都是从满足客户的要求出发，而不是通过系统的定性或定量分析。（7）人力资源缺乏首先，一些老国企由于历史的原因人员负担很重，需要承担离退休人员的费用。其次，物流人才缺乏。由于目前省内的物流业还不够发达，物流公司规模偏小，利润率偏低，再加上国内本身物流人才的稀缺，公司很难吸引本科及本科以上学历的人才，一线配送员工普遍是高中学历，经营管理人员普遍是中专和大专学历。尤其是综合型物流公司，它们提供的服务层次比较高，涉及的服务内容比较广，接触的客户的经营规模也比较大，非常
8、需要这类高素质高学历的人才，这使本省的综合型物流公司无法承接高层次的物流项目。从上面的分析可以看出，这些地区的物流发展还很落后，物流公司的规模不大，多属于中小型公司。并且，公司的配送网络覆盖面积不大，信息系统还不完善，如此等等，这些因素决定了公司的配送水平不高，无法进行复杂的配送或是在配送时只凭经验作出决定。因此，目前的物流物流公司配送方式还很简单，配送手段还比较落后，配送决策的制定也只是依靠经验，还没有对物流网络进行深入的研究和定量的分析。以上是从中小型物流公司的内部来说。从外部来看，物流市场的秩序现在还很不规范，导致了物流市场的混乱，妨碍了中小物流公司的公平竞争。首先，由于目前还没有相关的
9、法律法规或行业协会的限制，使得进入物流行业的门槛过低。只要符合工商管理部门注册资金的要求，不管是否具有相当的设施设备或条件，都可以注册成为从事物流业务的公司。这使得很多中小物流公司只有少量的资金就开始从事物流业务，一旦需要投入资金建设物流设施设备，这些公司就开始缺乏资金，运转困难。其次，在低端的物流市场（主要是中小物流公司竞争市场），由于中小物流公司鱼龙混杂，资质水平参差不齐，造成了严重的过度竞争、恶性竞争。例如在短途配送市场，各物流公司为了争夺市场份额，纷纷降低运价，导致整个配送市场低迷，运价低于成本，很多中小物流公司只能靠超载来维持生存。据了解，一辆20吨的货车将35吨的货物（超载75%）
10、从深圳运往珠海的运价仅为880元，而其中路桥费、油费加起来就有550元之多，即使不用扣除其他成本和费用，公司的利润也仅300元。如果加上人力等开销，成本可能将高于运价，公司无利可图。中小物流公司的现状非常令人担忧，照此下去，大部分的中小物流公司将会被淘汰出局。中小物流公司该如何完善自我，不断提高自身竞争力，已经成为了当务之急。因此，对中小物流公司的配送价格进行合理的安排就显得尤为重要了。物流公司在实践中决定去程配送的运价时通常是根据来回的配送成本制定的，也即考虑去程时的成本和返程空驶的成本，再加上其它成本，如过桥过路费等，最后给客户一个报价。因此去程的运价事实上已经可以补偿返程时花费的成本，出
11、租车的定价也是同理，因此返程带货赚取的是多余的利润，司机不太在意货物的价格，讨价还价的空间比较大，价格也会比较低。有时返程时碰到的客户急需将货物在短时间内运出，价格会相应偏高一些；对时间要求不强的货物价格相对较低。中小物流公司的车辆将货物运往目的地时，为了保证在约定的时间内到达，会按照客户的指定的某些地点直接运送，而不经停其它的地点，以保证货物准时快速地运达目的地，避免途中遇到无法预测的问题耽误时间。而返程时，车辆有充足的时间返回出发地。如果空车回去，车辆将白白浪费掉宝贵的配送资源没有任何收入。因此，为了不浪费车辆资源，司机常常绕路到其它地点带货回目的地。但是车辆必须在尽可能少的时间内赶回起点
12、，以便公司重新组织配送。由于无法获得各个地点准确的需求信息，返程时司机通常只能凭经验决定应该途经哪一些点。由于市场竞争激烈，报价时给出一个合理的价格非常重要。如果价格制定太高，客户会另寻物流公司；如果太低，物流公司可能要亏本经营。所以，大多物流公司常常会把返程时赚得的附加利润与客户分享，通过返程带货的利润来降低报价，从而赢得配送权，因此这个报价与返程的路径选择及利润紧密相关。当车辆途经的地点大多都有较高的价格，而且货运量也比较大时，返程车辆有较高的利润，那么在对去程配送的货物开价时就可能给出更低的价格。相反，如果车辆的路径选择不当，所经过的很多地点货物少且运价低甚至没有货物要空车驶回，那么车辆
13、在这条路径上可以获得的利润就会减少，在对去程客户开价时不得不给出较高的价格以保证不亏本。这样的路径选择问题也就是车辆路径问题（Vehicle Routing Problem, VRP）的研究范围。有所不同的是，VRP问题通常只以路径长度最短为目标，而在现实中，不仅要求路径长度较短，在有些情况下（如上面提到的情况），还要求利润最大。目前对这个问题，多数中小物流公司还是凭经验作决策。正如调研中所看到的，公司大多都还处于发展初期，信息化的水平很低，很难准确、实时地了解到其它地区的配送需求；由于资金积累不多，投入信息建设和供应链研究的公司很少；再加上公司人员素质不高，操作都以经验为基础，没有理论的指导
14、。因此，对去程时走哪条路最近，返程时哪条路线的利润更大，没有进行过数量分析。这极大的影响了物流公司价格的合理制定，从某种程度上导致了公司配送价格过低或不合理。本文着眼于此，针对国内中小型物流公司的现状，运用VRP模型，对物流公司车辆配送路径选择与价格策略建立了相应的数学模型，通过遗传算法的求解，可以获得一个可以使物流公司不亏损的路径，以及相应的公司可接受的最低运价；同时，运用博弈论的模型和方法，分析对客户与承运者之间的博弈关系，得出一个令客户接受的最高运价，这两个运价最后形成一个可行的价格范围，使物流公司在这个价格范围内既可以保住客户又能够保证物流公司不亏本。1.2 国内外研究现状本文研究的是
15、在路径选择基础上的配送定价，主要涉及到车辆路径选择问题及配送价格策略。这两个问题的研究现在还比较独立，暂时还未见将两者结合起来进行研究的文献。因此，在进行文献综述时，将这两方面的问题分别进行讨论。1.2.1 车辆路径选择问题研究现状车辆路径问题（Vehicle Routing Problem, VRP）是指对一系列发货点和收货点，组成适当的行车路径，使车辆有序地通过它们，在满足一定约束条件的情况下达到一定的目标。本文研究的重点在VRP问题上，即确定了车辆的终点和始发地，在终点与始发地之间存在多个地点，寻找一条路径，使车辆通过这多个地点中的某些地点，从而使车辆在一定的时间范围内，以最大的利润回到
16、始发点。车辆路径问题是1959年由G. Dantzig和Ramzer首先提出的2，分类方式主要有以下几种：根据安排路径前是否已知各节点的信息可以分为确定性VRP和不确定性VRP，其中不确定性VRP包括随机VRP（SVRP）和模糊VRP（FVRP）；根据约束条件分为带能力约束VRP（CVRP）、带时间距离约束VRP（DVRP）和带时间窗口VRP（VRPTW）。对于VRP的研究进展，已经有不少学者作了极其详尽的整理3，下面仅对VRP作简单的介绍。VRP的算法与建立的模型密切相关。由于学者们大多以确定性VRP和非确定性VRP进行分类，因此本文也以这种方式为主，辅以其它的分类方式。在现实生活中，车辆都
17、有负荷限制，因此，如果没有特别说明，讨论的都是带能力约束的VRP。1、确定性VRP现实中最常见的类型就是确定性VRP，它针对已知客户、节点的确切需求信息以及客户、节点位置的情况。实例包括物流中心对各超市要求配送的商品进行路径和流程的选择。以下是针对这种类型的问题的精确算法和人工智能算法。（1）精确算法精确算法包括以下一些算法：给定下界和相关的分枝定界算法。Lapore等人提出了这个方法，它利用了VRP和其放松形式m-TRP之间的关系4。根据Lenstra等人给出的的上界，-TSP可以转化为1-TSP。k度中心树及其相关算法。Christofides等人提出了此方法，它对固定m的m-TSP进行k
18、度中心树松弛5。M.L.Fisher对这个方法做了进一步的改进6。动态规划法。Eilon等人提出了这个方法，它的研究对象是固定车辆数的VRP，并运用递归方法求解7。为使计算规模减小，该方法引入了可行性规则或松弛过程以减少状态的数量。集分割和列生成。Balinski等人首先提出了该方法，因为其直接考虑了可行解集合并在此基础上进行优化，它建立的VRP模型最为简单8。Rao等人引入了列生成方法，将原问题简化9。从本质上说，这种算法是最短路径算法，同时又结合了分枝定界法。三下标车辆流方程。该方法由Fisher等人提出，主要针对带能力约束、时间窗口及无停留时间的VRP10。在方程中，两个下标表示弧或边，
19、另外一个下标则表示特定车辆的序号。二下标车辆流方程。此方法是由Laporte等人提出的，通过去掉表示车辆序号的下标，引入所需车辆数的下界，对称的CVRP和DVRP可以得到一个更为紧凑的方程11。与这个方程对应的算法结合了爬山法的思想，其核心还是线性规划。如果解是分数，可以用分枝定界方法求整数解。总之，因为使用的是严格的数学方法，精确算法在可以求解的情况下其解一般优于人工智能算法。但是也因此造成算法的局限性，无法避免指数爆炸问题，只能有效求解中小规模的确定性VRP。（2）人工智能算法对于中小规模VRP，精确算法的精度要高于人工智能算法。但对大规模VRP，人工智能方法却可以在有限时间内找到近优解或
20、可行解，在这一点上，精确算法无法与之相比。因此，人工智能算法在实际应用中更广泛。常见的有特色的人工智能算法有以下几种：Clarke-Wright算法。针对车辆数不固定的VRP，Clarke和Wright提出了该算法12。首先，按照不包含出发点在内的访问的点数，生成同样数量的路径，并计算合并任意两条路径后可以节省的成本。接着，对节省的成本量进行排序，根据排序结果和可行性条件归并路径，直到无法找到更好的解。在这里，归并指去掉位于原来两条路径中的弧(i,1)和(1,j)，用(i,j)代替。Golden，Nelson，Paessens等人运用适当的数据结构降低了这个算法的复杂度13。Sweep算法。W
21、ren，Gillett等人提出了这个算法，算法首先计算访问点的极坐标，并按角度的大小排序；接着在满足可行性条件的基础上，按角度大小归并到不同的子路径中；最后，根据TSP的优化算法对得到的子路径进行优化14。Chrisofides-Mingozzi-Toth两阶段算法。这个算法主要针对的是CVRP和DVRP，算法为两个部分：首先，按最小路径原则得到初始解，然后用k-OPT算法优化各子路径；接着为了减小总行程，在各子路径间交换点，使用k-OPT算法对点交换后的子路径进行优化15。禁忌搜索。该方法最早是由Gendreau等人应用于VRP。它首先构造一系列解，然后对得到的解不断进行改进16。该算法的解
22、可能是非可行解，通过使用目标函数里的罚函数表示其对可行性的偏离程度。通过GENI过程，得到求解过程中的邻域的。后来E.Taillard等人实现了求解的并行化。他按照角度和路径重心对原问题的空间进行了分割，然后使用禁忌搜索结合模拟退火方法求解子问题17。遗传算法。这个方法可有效求解带时间窗的VRP问题。首先将这个方法应用于VRP研究的是J.Lawrence18。Barnier将它与约束满足问题(CSP)技术相结合，减小搜索空间，降低CSP目标函数和遗传算法约束的复杂度19。其中，基因的适应度是通过对CSP解的计算得到的。在国内，张涛等人使用遗传算法确保搜索的全局性，使用3-OPT算法保证局部搜索
23、能力，从而得到面向VRP的混合算法20。重复匹配。P.Wark等人首先提出这个方法。方法开始时为每个客户生成一条子路径，然后参照总匹配成本和负载改变匹配成本归并路径，并为满足自匹配条件的集合提供了分割方法，使其可以跳出局部最优21。2、非确定性VRP（1）随机VRP如果要访问的节点数量和位置不变，每个顾客每天需求不同，且这些需求满足一定分布，调度员由于时间和信息有限，有时必须在获得所有信息之前就作出决策，这时就要运用本节讨论的随机VRP方法。中心邮局对各邮政支局的取邮件服务等就属于这类问题。现在已有的算法大多为以先验（即定）序列为基础的方法。这个方法包括两个阶段：首先在信息不完全的情况下确定先
24、验序列，然后在获得确定性信息的时候决策。所以，其随机模型的选择取决于第一阶段的成本和第二阶段的期望成本。其先验序列的确定方法又包括两类：按二元可能性理论和基于机会约束规划。Jaillet博士在他的论文中最早提出了第一类方法的思想，Bertimas在其博士论文中基本建立了完整的体系22,23。这个方法假设需求分布是二元、离散的，继而可以推导出先验序列的期望长度、相应的上下界和渐进特性。以该理论为基础，Michel Gendreau等人对算法进行了改进24,25。第二类方法是由Stewart，Dror，Laporte等人提出的26,27。这个方法的核心是使出错返回的概率不超过某一界限。前面提到的学
25、者们分别运用机会约束规划，在一定的假设条件基础上，把SVRP转化为等价的确定性VRP，同时找到了解的界。确定性VRP的三下标流和二下标流模型是机会约束规划模型的基础，确定性算法与这类算法也有相似之处。例如M.Dror就是在建立三下标流机会约束规划模型和罚函数模型的基础上，运用Clark-Wright算法求解的28。在第二阶段，算法的策略是跳过需求为0的节点直接访问下一个节。如果车辆在某个节点的载重量超过了车辆可以承受的最大重量，就返回出发点卸载货物，然后回到出现超载的地方继续服务。随机VRP还包括位置路由问题（LRP）和需求可切分的SVRP等问题，但这些问题迄今为止都是以基本型SVRP为基础的
26、。在仓库运作成本已知和使仓库运作成本最小的条件下，LRP需要确定各仓库的位置和最优配送路径。B.Bouzaiene-ayari等人则利用Dror等建立的模型和算法求解需求可切分的SVRP问题29。（2）模糊VRP现实中，配送系统的某些需求信息没有或难以给出准确的描述，如：“大约20千克”，“10到15单位”，“有几个玩具的小箱子”。这类问题的研究最早是由D.Teodorovic等人进行的，核心是基于Sweep算法的30。他用模糊数代表某个节点上的需求信息，在倾向度的基础上建立模糊判定规则。后来祝崇隽、刘民、吴澄等人建立了基于置信度的三下标流模型，提出了基于可能性分布的2-OPT算法31。目前国
27、内对于VRP的研究仍处于起步阶段，研究的文献在1999年后才逐渐增多。在国内的核心期刊上发表的关于VRP问题的文章很少，而且一般都是就确定性问题进行讨论，运用的方法大多为启发式算发，如遗传算法和蚁群算法等32-42。我国对VRP问题的研究现状远不能与蓬勃发展的物流、配送业务相匹配。1.2.2 物流配送定价研究综述在对文献进行物流定价搜索时，发现国外大多数文献是关于道路的过路费定价43及航空配送定价44-46的，对地面配送的定价文章暂时没有搜索到，可见在这方面做的研究还很少。这可能与国内外的物流发展水平相关。发达国家如美国、加拿大、澳大利亚的物流水平远远超出国内现状，通常物流公司拥有固定的客户和
28、完备而且庞大的配送网络，车辆来返程都有充足的货源，并可以通过信息系统获得最新的需求资料，因此，在配送上更多的考虑的是服务质量，也即努力缩短配送时间，而不需要考虑返程带货的利润。而且，这些国家的物流行业已经成熟规范，价格的浮动不大，主要还是以质取胜，因此，对这方面的研究就相对较少。相比较而言，国内在这方面的研究比较多。陶表益，赵浩兴认为物流供应价格取决于物流供应方在具体功能上的影子价格47。物流供需双方获得最大利差时，物流供应方实现物流影子价格的总和等于完全竞争市场上的价格水平，而物流服务需求方实现了单位价格的边际效用均等。实现了社会效益最大，整个物流市场处于交易均衡的理想状态。任何偏离这一平衡
29、状态的现象,在市场机制的驱动下,最终会趋于均衡的价格水平。兰永红从物流服务定价的参与者物流公司和客户的目标着手，构建了物流服务定价的两阶段博弈模型，在完备假设的基础上分析了物流服务定价策略，并由此提出了制定合理物流服务价格的若干建议48。鞠廷英研究了如何在政府对运价放松管制的条件下，科学合理地调整价格，是提高公司经济效益和竞争力的关键49。文章利用经济学原理给出了一种调价模型，对影响价格的若干因素如竞争对手的实力，消费者对运价承受能力等采用专家或决策者的经验知识进行评估，得到各因素对运价影响的显著性，并对该模型进行了修正，最后通过实例验证是可行的。1.3 本文主要研究内容和技术路线为了简化模型
30、，传统的VRP问题有许多严格的约束条件。随着研究的深入，这些条件逐渐调整以便模型更加与现实相符，出现了如动态VRP，带时间窗的VRP，带返程的VRP等，并将路径长度的最优化作为目标。现实中的情况可能复杂的多，经营者们也并不仅以路径最短为目标。中国现在不少物流公司的发展水平不高，面临的情况是：车辆要将客户的货物运送到已知的几个地点，然后车辆将返程回到出发点。返程过程中，车辆通常都会沿途带货以赚取额外的利润，而车辆所经过的地点是不确定的，数量和价格也不确定，通常司机会根据自己的经验来判断返程经过的地点。经营者们将返程带货的额外利润中的一部分返回初始的客户，即降低它的配送价格，如果能够使返程货的利润
31、充分大，就可以尽量压低去程时的配送价格，从而使公司具有更强的竞争力。因此，如果能找出令返程利润充分大的路径，就可以根据返程利润和已知的去程成本，计算出去程时的最低配送价格。本文根据以上内容进行数学建模并给出算法，将配送路径上的利润引入到路径选择过程中，并将利润的最大化作为目标函数。车辆在去程时必须首先将客户的货物送到已定的地点。此时假设客户为满载配送，配送价格待定，需要根据返程利润计算；配送成本已知，因此去程可以简化为一个传统的VRP问题，不同的是车辆并不立即返回出发地。车辆在返程时可以自由选择是否经过某个地点，而不是必须经过所有的地点。这使研究更加接近现实，所得的结论也更有利于实际应用。一般
32、说来，承运人在得到最低运价后，为了能够获得利润，会向客户提供一个略高的价格。但是物流市场中竞争者很多，如果价格报得太高，就可能失去客户。因此，本文运用博弈论的方法，对承运人与客户及承运人之间的价格博弈进行研究，从而得到承运者在已知自己最低运价的情况下，可以报给客户的最高运价。如果超出这个价格，客户就会放弃与承运人合作。本文第一章是绪论，介绍了本文的研究背景及意义，并分析了国内外相关研究的现状；第二章对本文研究所用的相关理论基础进行了概述；第三章对去程单一目的地的路径优化问题进行了研究，并设计了数学模型进行求解；第四章对去程多目的地的路径优化问题进行了研究，并设计了数学模型进行求解；第五章针对客
33、户与承运者之间的博弈模型进行了分析、计算；第六章是结论和展望。根据本文的研究内容，论文研究的技术路线如图1.1所示。模型遗传算法算例模型遗传算法算例去程单一目的地的路径优化及定价去程多目的地的路径优化及定价物流公司发展现状VRP研究现状最低运价最高运价总结与展望返程利润最大化为目标博弈论图1.1论文研究的技术路线图综上所述，本文的创新之处在于以下两点：（1）返程寻找路径时以利润最大化为目标。（2）将一级密封拍卖原理应用于承运者之间的价格博弈。由于本文研究对象的特殊性，对一些方法进行了应用或改进：（1）在对返程问题进行数学建模时，由于本文的研究对象与VRP中的研究对象有所区别，因此对模型中的变量
34、进行了改进，不再以一个0,1变量代表车辆是否经过一条路径，而以两个0,1变量的乘积表示，这两个变量各自均表示在某一时刻车辆所在的点。（2）针对所建模型的求解复杂性，本文采用了遗传算法，并在染色体表示中，对基于顺序表示的基因编码方法进行了改进，使其更适用于研究对象的表示。81 第二章 相关理论基础第二章相关理论基础本文研究的问题主要建立在以下三个理论基础之上：车辆路径问题（VRP）、遗传算法以及博弈论。本章首先针对以上三个理论基础进行介绍与阐述，为该理论模型的应用打下基础。VRP是一个在世界范围内被广泛研究的问题。而本论文的研究重点是一个与VRP有关的路径优化问题，不同的是本文研究的问题要考虑带
35、返程的配送问题，且要考虑返程配送利润的问题。本章中的一般VRP即学者们普遍定义和研究的路径选择问题，它有别于本文中提到的路径优化，但基本原理是类似的，都是在多个城市或节点中寻找可以令目标函数如路径长度最优的过程。2.1 车辆路径问题概述2.1.1 一般车辆路径问题的特征和目标关于仓库和用户之间的货物配送问题通常被称为VRP问题，即车辆路径选择问题。货物的配送涉及到在给定时间内，通过一条适合的公路网络，由一个或几个仓库的车辆为一系列的客户提供服务。这些车辆由驾驶员操作。一个VRP的解决需要确定一系列的路径，每条路径由一辆开始并结束于仓库的汽车通过，由此使所有的顾客的要求和操作约束条件得到满足，总
36、的配送成本最小50。在这里，通过考虑路径选择的主要要素，包括公路网络、顾客、仓库、车辆和驾驶员，构成路径的操作约束和最优化过程中可能的目标来描述其典型的特征。（1）公路网络的特征公路网络通常用图来表示，边表示不同的路段，顶点代表交叉路口。边可以是有向的也可以是无向的，这取决于他们是只能单方向行驶（比如现在的单行线）还是可以双向行驶。每一条边都与一个成本相联系，这个成本通常代表长度和行驶时间。（2）顾客的典型特征顾客位于公路网络的顶点；货物必须在顾客点卸下或收集；顾客在时间窗内获得服务，例如，由于交通的限制，有些顾客只在特定的时间内接受服务，有的地点只有在特定的时间内才能进入；在顾客处卸下或收集
37、货物所需要的时间可能依赖于车辆的类型；由于有些车辆的限制或者是由于装卸的要求，有些车辆可能无法获得。有时，不是每一个客户的需求都能得到满足，在这种情况下，装卸的货物量或者一部分客户可能无法得到服务。为了解决这种情况，可以为客户分配无法得到部分或全部服务时的不同的性质（priority）和惩罚（penalty）。（3）仓库位于公路网络的顶点，为客户提供服务的车辆路径开始并结束于一个或多个仓库。每一个仓库的特征为这个仓库的车辆的数量和种类，以及仓库总的货物数量。（4）车辆用来配送货物的工具。车辆的组成和大小可以是固定的也可能根据客户的要求确定。与车辆相关的要素为：车辆的始发仓库，以及车辆回到另一个
38、仓库的概率；车辆的容量，用车辆可以装载的最大重量，体积或托盘数量来表示；将车辆分成几个可能的隔间，每一个隔间由它的容量和运载的货物的种类来表示；装卸时可以使用的工具；车辆可以通过的公路的图的边的子集；使用车辆的相关成本（每距离单位、每时间单位、每条路径等）；驾驶员必须满足一些合同和公司规定的约束，比如白天的工作时间，服务中的休息次数和时间等。在问题的讨论中，驾驶员的约束被嵌入到与之相关的车辆的约束中。（5）路径路径必须满足一些操作的约束，这取决于配送货物的性质，服务水平的质量，以及顾客和车辆的特点。一些典型的操作约束如下：在每一条路径，车辆现有的载重量不能超过车的容量；在一条路径上的顾客可以要
39、求收获或发获服务，或者同时要求这两种服务；顾客只能在它们的时间窗以及司机的工作时间内接受服务；VRP问题有几种目标，典型的目标为：根据所有的配送距离或配送时间以及使用车辆的固定成本，使全局配送成本最；使为顾客提供服务的车辆或司机的数量最小；根据行驶时间和车辆载重，对路径进行平衡；对部分顾客服务的惩罚最小；或者是以上目标的整合。VRP最基本的数学模型如下所示： (2.1)s.t. , (2.2) , (2.3) (2.4) (2.5), (2.6)式(2.2)和(2.3)是入度和出度限制，使每个点只有一个弧进入并且只有一个弧从此点出去。类似的，式(2.4)和(2.5)限制了出发点的入度与出度。2
40、.1.2 车辆路径问题基本类型自从Dantzi和Ramser提出VRP问题已经过了四十多年，在他们的著作中，作者描述了一个关于将汽油运送到加油站的VRP实际应用问题，并且提出了第一个数学规划方程（mathematical programming formulation）以及解决问题的计算方法2。几年后，Clarke和Wright改进Dantzi-Ramser算法，提出了一个有效的贪婪算法（greedy heuristic）12。在这两个开创性的论文之后，学者们对不同类型的VRP问题的最优及近似解提出了许多模型、精确及启发式算法。以下介绍一些最重要最有效也是最基本的模型和算法。（1）有容量和距离
41、约束的VRP问题（capacitated and distance-constrained VRP, CVRP）有量约束的VRP问题(CVRP)是VRP的最基本问题。在CVRP中，所有的顾客都接受配送服务，顾客的需求是已知的、确定的，且需求不能分开接受服务。车辆是一样的，并且都停在一个中心仓库。车辆只有容量约束。目标是使车辆为所有顾客提供服务的总成本（也就是路径数量和长度或配送时间的函数）最小。（2）带时间窗的VRP问题（VRP with Time Windows, VRPTW）VRPTW是CVRP的扩展。在这个问题中，车辆有容量约束，每一个顾客都与一个时间段相ai,bi联系，这个时间段称为时
42、间窗。车辆只能在给定的时间窗内开始为顾客提供服务。如果车辆在时间窗之前到达，通常必须等到后开始服务。（3）带返程的VRP问题（VRP with Backhauls, VRPB）VRPB是CRVP的扩展。在这个问题中，顾客集被分成两个子集。第一个子集L，包含n个去程顾客，每个顾客需要一个给定数量的货物。第二个子集B，包含m个返程顾客，车辆必须提取给定数量的货物。在VRPB中，去程和返程顾客之间存在着优务先约束：当一条路径中包含两种类型的顾客时，所有的去和顾客必须在返程顾客之前得到服。当成本矩阵是非对称的，这个问题可以称为非对称带返程的VRP问题AVRPB（Asymmetric VRP with
43、Backhauls）。VRPB（以及AVRPB）要找到K条令成本最小的圈（simple circuit）并满足：每一个圈必须访问仓库；一个顾客只能在一条圈中；一个圈中的去程货物需求量和返程货物需求量都不能超过汽车容量C；在每一个圈中，必须先访问去程顾客，再访问返程顾客。（4）带收取和配送的VRP问题（VRP with Pickup and Delivery, VRPPD）在这个问题中，车辆可以为一个顾客配送货物后再收取这个顾客的货物，并在配送途中将货物运给下一个目标顾客。对每一个顾客i，Oi表示i点的配送需求来源于这个顾客，Di表示在i收取的货物的目的地。假设在每一个顾客点，配送在收取货物之前
44、发生。因此，车辆在到达一个给定点之前的载重量是初始载重量减去已经配送的需求量再加上已经收取的货物量。VRPPD由K个令成本最小的圈组成，并满足：每一个圈必须访问仓库；一个顾客只能在一条圈中；车辆在圈中的载重量非负并且不超过汽车的容量；对每一个顾客i，顾客Oi（当它不是仓库）必须在同一个圈内在之前先得到服务。对每一个顾客i，顾客Di（当它不是仓库）必须在同一个圈内在i之后得到服务。图2.1表示了各种类型VRP的基本类型及联系。CVRP有容量限制的VRP问题DCVRPVRPTWVRPBVRPPDTWVRPPDVRPBTW时间窗返程混合服务路径长度图2.1VRP基本类型及联系通过以上对VRP的基本介
45、绍，可以了解VRP的特征和基本类型。根据以上内容所述，本文所研究的是一个带容量限制、带返程的路径选择问题，并有其特殊性。在研究返程的路径选择时，由于返程主要是在一定时间内回到出发地，并为物流公司提供多余的利润并与客户分享利润，因此，返程不再以路径长度最短为目标，而是以利润最大为目标；研究去程访问多个地点的配送时，由于要尽量使货物在短时间内到达，因此不再以利润最大为目的，而以经过所有客户指定地点的路径最短为目标，也就是学者们经营研究的VRP。2.2 遗传算法概述2.2.1 遗传算法理论基础自从1975年John. H. Holland教授在著作“Adaptation in Natural and
46、 Artificial Systems”中3正式提出了遗传算法的基本概念以来，经过短短二十多年的发展，作为一种适合大规模操作的智能算法，遗传算法不仅在理论上日趋成熟，而且在工程应用上也得到丰硕的成果，得到越来越多的研究者的关注，它为人工智能算法的实施与应用指明了一条重要的道路。1、遗传算法的基本概念遗传算法是一种模拟生物进化过程的学习方法，它操作的对象是由多个个体构成的种群，通过对种群中的成员模拟生物进化的方式来产生下一代种群，新种群总是在旧种群的基础上获得改进和提高，周而复始，从而使得种群的整体质量朝着优良的方向发展。由于遗传算法是借鉴生物进化的思想，所以，遗传算法仍然沿用生物学中的一些术语。染色体（Chromosome）（个体,Individual）：它是遗传算法中的运行的最基本的单位，是特定问题在算法中的表现形式，一般由二进制的数串所组成；基因（Gene）：它是染色体的最小组成单位，在二进制数串中它由一个数位来表示；基因片（Gene Slice