管理研究方法.pptx

2015级硕士研究生课程管理研究方法专题之数学建模与优化仿真陶 毅广东工业大学 管理学院3考虑作业均衡的泊位堆场联合分配问题21带三维装载能力约束的路径规划问题航空货运装载规划问题集装箱转运码头什么是转运？为什么堆存很关键？研究背景泊位堆场联合分配作业量定义数学建模三阶段方案(1)Stage 1: Determining the size of each cluster三阶段方案(2)Stage 2: Deciding berth and yard allocation三阶段方案(3)Stage 3: Assigning exact location for each cluster3考虑作业均衡的泊位堆场联合分配问题21带三维装载能力约束的路径规划问题航空货运装载规划问题路径规划问题(1)234路径1路径251车场6路径387Vehicle Routing Problem，简称VRP路径规划问题(2)要素描述车场(配送中心)进行集货、分货、配货、送货作业的仓库、车站、港口、车场等,其数量可以是一个或者多个;属性: 车场的位置、所配备的车辆类型和数量、所供应的货物类型和数量等;车辆货物的运载工具;属性: 车辆的类型、最大装载量、一次配送的最长行驶距离或最长行驶时间、所属车场、完成任务后的停放位置等;客户接受服务的对象;属性: 客户所处的位置、需求或供应的货物的种类和数量、允许接受服务的时间段、服务所需要的时间等;货物物流配送的对象，可以将每个客户需求的货物看成是一批货物;属性: 货物名、包装、重量、体积、形状、要求送达的时间和地点、能否分批配送等;运输网络从图论的角度看,物流配送中的运输网络可以看成是一个无向图;约束条件客户对货物品种、数量的要求;客户的优先级、车辆类型、货物发到的时间窗要求;车辆的最长行驶距离、最长工作时间和最大装载量要求等;目标函数运输总里程最短;成本最低;准时性最高;运力利用最合理;VRP问题要素(Toth和Vigo,2001; Cordeau等,2007)I41I42d4=10I11I12d1=40I52I51d5=30I21d2=25I63I61I62d6=35I71d7=15问题描述(132I31I33d3=30D=100问题描述(2)带三维装载能力约束的路径规划问题（Three-Dimensional Loading Capacitated Vehicle Routing Problem,3L-CVRP)车场(配送中心)单一;已知可提供的货物类型和数量等;车辆单一类型;已知可用车辆数量、最大装载量;装载空间三维;客户已知所处的位置、需求货物的种类和数量;无服务时间窗限制;货物已知重量、体积和要求送达地点;不允许分批配送;形状三维;运输网络每条边的距离和路径成本已知且对称;目标函数总路径最短/总成本最低;约束条件车辆完成任务后必须返回原车场;每个客户有且仅有一辆车服务,客户需求的货物必须完全装入同一车辆;每辆车要装载其服务的所有客户所需的所有货物,即所有客户的需求都要得到满足;载重量约束;一系列三维装载约束;问题描述(3)约束约束名称约束条件描述约束1典型三维装载约束货物之间不允许重叠,货物的任何部分都不能超出车箱空间;约束2正交摆放约束货物必须正交地放入车厢中,即货物的三边都要与坐标轴平行;约束3旋转、翻转约束货物在摆入车厢时只允许以边作为高,其另外两条边所构成的底面可以做90度的旋转;约束4易碎品约束易碎品上面可以堆放易碎品,但不能堆放非易碎品;非易碎品上面即可以堆放易碎品和非易碎品;约束5支撑面积约束当某个货物放在其他货物上面时,需要有一定量的支撑面积对其进行支撑;约束6后进先出规则在装货时后放入车箱的货物要先取出(Last In First Out)问题描述(4)yy高H装载点xI12I11x车箱门z宽Whihili长Lwiwiliz后-左-底点约束3示意图I41I42d4=10I11I12d1=40I52I51d5=30I21d2=25I63I61I62d6=35I71d7=15问题描述(532I31I33d3=30D=100问题描述(6)0y1I11I12I322I21xI21I31I333I12I11I31I32I33z0基于最小浪费装载法则的装箱算法(1)主问题装载子问题生成相应的货物序列主问题生成一条路径生成相应的客户序列对货物序列进行排序依次枚举每一个货物依次枚举该货物的摆放方式依次枚举每一个装载点方案可行?计算每个可行方案的得分按得分最高的方案装载货物更新可行装载点集合基于最小浪费装载法则的装箱算法(2)yyxxI11zzyyI21xxI12I12I11I11zz基于最小浪费装载法则的装箱算法(3)浪费最小浪费装载点闭包概念：将已经装载的