网络中供需匹配与多批次取送货车辆路径问题研究

发布时间：2020-12-17 23:35

　　本论文研究了供需匹配与多批次取送货车辆路径问题。在此问题中,客户点之间的供需匹配关系事先未知;每个客户点的取货请求和送货请求允许通过多次访问该客户点来分批次满足;需做供需匹配决策和车辆路径决策。此问题是经典车辆路径问题的一种复杂衍生体,普遍存在于国际原油运输、烟草制造行业中的生产原料调拨、零售行业中的商品库存重新布局及共享单车系统中的自行车重新分配等网络中。基于此问题高度复杂且受到的关注较少,本文分别从模型建立、启发式算法求解和精确算法求解的角度对此问题进行深入研究。本文的主要研究成果呈现如下:(1)本文所研究的问题包含了两个相互影响的决策:供需匹配和车辆路径。先建立一个混合整数线性规划模型作为基础模型。然后,通过消除两个决策变量之间的耦合关系,提出一个新颖的单元化模型。紧接着,提出一系列多项式型有效不等式来加强单元化模型。实验结果表明,单元化模型比基础模型更容易求解,且所提出的有效不等式显著地提高了单元化模型的性能。最后,验证了所提出的模型和不等式对文献中相关问题的有效性。(2)为快速求解现实中的较大规模的问题,基于所提出的单元化模型,先设计一个贪婪式算法来构建初始解。然后,基于优化... 

【文章来源】：华中科技大学湖北省 211工程院校 985工程院校 教育部直属院校

【文章页数】：132 页

【学位级别】：博士

【部分图文】：

图１－１研究的技术路线??１．４论文总体结构与主要内容??

目前烟草行业中的生产原料调运模式也属于单次访问的情况。直观上看，允??许＂多次访问＂（即单车多次访问一个客户点）使得问题的优化空间更大，带来更多??的经济效益。如图３－１所示，假设网路中有３个王厂、４种生产原料且车辆的最大装??载量为３个单位。每个工厂的供应信息和需求信息如列＂供应＂／＂需求＂所示，其??中括号中的数值表示生产原料的供应／需求量。所有车辆必须从车场出发，执行运输??任务后返回到车场且每辆车最多被使用一次。在单次访问模式下（如图３－１?（ａ）所??示），需要两辆车来满足所有工厂的需求，路线分别是：车场一工厂１?一工厂２?—??工厂３?—车场（实线部分）和车场一工厂３?—工厂１?一工厂２?—车场（虛??线部分）。车辆从一个工厂到另一个工厂的装载信息呈现在两个工厂之间的连线上。??然而，在多次访问模式下（如图３－１?（ｂ）所示），Ｗ上两条路线可Ｗ合并。即只需一??辆车就能完成运输任务且相应的路线为；车场一工厂１?一工厂２?—工厂３?—工??厂１?一工厂２?—车场。与单次访问的调运模式相比，单车访问了工厂１和工厂２??两次。显然，多次访问模式下的调运方案比单次访问模式下的运输方案需要更少的??运输车辆和运输成本。因此，多次访问模式下的调运方案更优。??原料：＾一画?＜３

一个＂单元化＂方法来化简基础模型，把化简后的模型称作＂单元化＂模型。??单元化方法的主要思想是顶点拆分。为了方便，本文用＂节点＂表示从原顶点??拆分出的子顶点。图３－２通过列举一个简单的例子来说明顶点拆分过程。图３－２中的??顶点供应２种产品，需求２种产品。??巧点?Ｉ?（供应?１?个单位）▲??供应?节点２?（供应１个单位）▲??节点３?（供应１个单位）▲??／Ｊｉ＾?Ａ?（ｇ）节点４?（供脚个单位）参??／?３个单位?＼?节点５?（供应１个单位）＞????－?叫??ｍｍ?紛?节点６?（需求３个单位）??３?个单位??需求?（＃＾?巧点７?（需求２个单位）〇??图３－２?—个顶点的拆分过程??基于Ｗ上顶点拆分过程，每个顶点根据供应和需求信息，拆分成一个或两个节点??集合。这些节点和原顶点的位置坐标相同。其中一个为供应节点集合，该集合中的每??个节点只供应一种产品且供应量为１。因此，拆分出的供应节点数等于原顶点针对所??有产品的总供应量。另一个为需求节点集合，在该集合中，每个节点只需求一种产品??且需求量等于原顶点对该种产品的需求量。因此，拆分出的需求节点个数等于原顶点??■所需的产品类型数。例如，在图３－２中，该顶点供应５个单位的产品，需求２种产品??类型


本文编号：2922910