带重心约束的集送货一体化车辆装载调度问题的研究

《带重心约束的集送货一体化车辆装载调度问题的研究》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、重庆大学硕士学位论文1绪论种状况：道路的90%都需要缴纳道路通行费，特别是跨城或者是同城高速，即车辆在配送货物的行驶过程中，无论车辆是空载还是满载，都需要缴纳道路通行费。为了克服单一正向物流或逆向物流存在的车辆高空载率、不利于环境保护以及配送成本高的缺陷，采用集送货一体化的思想将配送过程和集货过程这二者统一起来已成为人们越来越关注的问题。于是，近年来兴起了一股研究集送货一体化车[1-3]辆路径问题（VehicleRoutingProblemwithSimultaneousDeliveryandPickup,V

2、RPSDP）的热潮。集送货一体化车辆路径问题的理论研究在探索中取得了一些成果，并在实践中取得了初步应用。良好的应用效果的展现又进一步推动了业界对该问题的深入[4]研究。美国州商业委员会新闻报告估算运输时使用回程集货每年可节约4200万加仑燃料；Kearne总结了企业在1978年到1983年间为了提高物流的多样性而执行的项目，第一个项目就是协调开出的车和返回的车从而提供自有车辆的回程集[5]货，这项项目已被83%的支持者采用；1986年沃尔玛公司用集送货一体化的思[6]想为车辆分派线路，每年节约成本约为450，

3、000美元；日本道路货物运输企业中的特别混装货物运输企业（以不特定多数货主为对象，从事多对多的运输工作，以运输和运送时间为主要因素的运输服务企业）的典型代表“宅配便”，利用先进的信息平台寻找货源，提倡集送货一体化，降低了成本，提高了服务水平。这些成功运作的案例对国内外的第三方物流企业都有一定的借鉴意义。集送货一体化的思想在实际生活中有着广泛的应用。如软饮料厂商需要把可乐等产品运送给杂货店，同时又需要把杂货店收集的空瓶回收到工厂；纯净水公司把纯净水送给客户的同时，需要从客户处收回用完的空桶；制造企业需要把原材料

4、从供应商处运送到仓库，同时又需要把生产出来的产品送给客户，苏果配送重心对每个社区超市送货的同时，回收退回的货物等。这些公司如果采用集送货一体化的思想实施运输管理，必将能够节约成本，提高服务水平。1.2国内外研究现状对物流配送的研究主要可以分为车辆装载和车辆调度两个方面，很多学者将车辆装载问题和车辆调度问题分开来单独研究，近年来，也有学者将两者结合在一起考虑。下面对这三种车辆问题分别简述一下其研究现状。1.2.1车辆路径问题的研究现状车辆装载问题（VehicleFillingProblem,VFP）是指在一定的

5、约束条件限制下，将配送计划所要求的一批货物按照适当的装载方法分别装入适合车型的车厢中，在满足配送要求的同时，使车辆装载容积和装载重量方面的利用率最高，使所选车型最经济，从而增加货物配送中对车辆的合理有效使用，降低运输成本提高经2重庆大学硕士学位论文1绪论济效益。VFP模型的目标函数一般为车辆装载重量的利用率最高、装载容积率最高或者是两者都能达到最高。模型中的约束条件大致可以分为以下两点：（1）装载进车厢的货物的总重量不超过车辆的有效载重量；（2）装载进车厢的货物的总体积不超过车辆的有效容积。George和Ro

6、binson采用构造型启发式算法来解决集装箱装载问题，使用“层”来生成摆放模式，建立沿着集装箱宽度的层，尽量使某一层的外表面平整，并且[7]结合剩余空间以提高空间利用率。但是当小物体数量多，大物体数量少时，则会使小物体优先放入，导致大物体被剩余，从而降低了空间利用率。Bischoff和Marriott比较了14种基于“层”的方法，层与层之间既关联，又独立存在，所以一个完整的布局模式中，为了更容易地满足一些约束，这些层的顺序[8]可以任意调整。LodiA等提出最大接触周长优先的启发式方法求解装载问题，同样也是根

7、据货物的装载顺序，计算该货物在所有可能填充的位置上与周围货物(包括车厢壁)[9]的接触周长，选择接触周长最大的位置放置该货物。BurkeEK等提出一种“bottom-leftfill”的启发式装载方法，主要是在算法中建立一个存放货物摆放位置的列表，根据货物的装载顺序，每次选择最左边最下边[10]的一个位置进行填充。姜义东提出了空间分割的启发式算法，采用三叉树的数据结构来处理空间，[11]该算法采用优先放置体积大的物体的策略，每次都先把最大物体放入剩余空间。每放置一个物体，就把当前空间划分为三个小空间，然后再逐

8、个对小空间进行空间填充。虽然这样划分剩余空间会减少问题的复杂性，但划分后的剩余空间比较“零碎”。樊建华的算法与姜义东的算法类似，采取优先放置边长较长的物体的策略，不同的是她优先考虑多个同类物体并排放置，刚好能在空间底面的宽度或长度方[12]向放满的情况，这样可以减少空间碎块的产生，降低空间的复杂性。卜雷、袁新江等应用改进遗传算法优化铁路车厢单箱三维装箱问题，考虑货[13]物放置方向、装载容积、装载质