1、货物配送问题【摘要】本文是针对解决某港口对某地区 8 个公司所需原材料 A、B、C 的运输调度问题提出的方案。我们首先考虑在满足各个公司的需求的情况下，所需要的运输的最小运输次数，然后根据卸载顺序的约束以及载重费用尽量小的原则，提出了较为合理的优化模型，求出较为优化的调配方案。针对问题一，我们在两个大的方面进行分析与优化。第一方面是对车次安排的优化分析，得出公司顺时针送货，公司逆时针送货为最佳方案。第二方面我们根据车载重相对最大化思想使方案分为两个步骤，第一步先是使每个车次满载并运往同一个公司，第二步采用分批次运输的方案，即在第一批次运输中，我们使A材料有优先运输权；在第二批次运输中，我们使B
2、材料有优先运输权；在第三批次中运输剩下所需的货物。最后得出耗时最少、费用最少的方案。耗时为40.5007小时，费用为4685.6元。针对问题二，加上两个定理及其推论数学模型与问题一几乎相同，只是空载路径不同。我们采取与问题一相同的算法，得出耗时最少，费用最少的方案。耗时为 26.063 小时，费用为 4374.4 元。针对问题三的第一小问，我们知道货车有 4 吨、6 吨和 8 吨三种型号。我们经过简单的论证，排除了 4 吨货车的使用。题目没有规定车子不能变向，所以认为车辆可以掉头。然后我们仍旧采取公司顺时针送货，公司逆时针送货的方案。最后在满足公司需求量的条件下，采用不同吨位满载运输方案，此方
3、案分为三个步骤：第一，使 8 吨车次满载并运往同一公司；第二，6 吨位车次满载并运往同一公司；第三，剩下的货物若在 16 吨内，则用 6 吨货车运输，若在 78 吨内用 8 吨货车运输。最后得出耗时最少、费用最省的方案。耗时为 19.6844 小时，费用为 4403.2。一、 问题重述某地区有 8 个公司(如图一编号至)，某天某货运公司要派车将各公司所需的三种原材料 A,B,C 从某港口(编号)分别运往各个公司。路线是唯一的双向道路(如图)。货运公司现有一种载重6 吨的运输车，派车有固定成本 20 元/辆，从港口出车有固定成本为 10 元/车次(车辆每出动一次为一车次)。每辆车平均需要用 15
4、 分钟的时间装车，到每个公司卸车时间平均为 10 分钟，运输车平均速度为 60 公里小时(不考虑塞车现象)，每日工作不超过 8 小时。运输车载重运费 1.8 元/吨公里，运输车空载费用 0.4 元/公里。一个单位的原材料A,B,C 分别毛重 4 吨、3 吨、1 吨，原材料不能拆分，为了安全，大小件同车时必须小件在上，大件在下。卸货时必须先卸小件，而且不允许卸下来的材料再装上车，另外必须要满足各公司当天的需求量(见表)。 问题：1、货运公司派出运输车 6 辆，每辆车从港口出发(不定方向)后运输途中不允许掉头，应如何调度(每辆车的运载方案，运输成本)使得运费最小。2、每辆车在运输途中可随时掉头，若
5、要使得成本最小，货运公司怎么安排车辆数？应如何调度？3、(1)如果有载重量为 4 吨、6 吨、8 吨三种运输车，载重运费都是 1.8 元/吨公里，空载费用分别为 0.2，0.4，0.7 元/公里，其他费用一样，又如何安排车辆数和调度方案？(2)当各个公司间都有或者部分有道路直接相通时，分析运输调度的难度所在，给出你的解决问题的想法(可结合实际情况深入分析)。图唯一的运输路线图和里程数公司材料A41231025B15012423C52424351表各公司所需要的货物量二、模型假设1) 港口的容量足够大，多辆运输车同时到达港口时不会发生阻塞现象；2) 多辆运输车可以在港口同时装车，不必等待；3)
6、双向道路上没有塞车现象；4) 8 个公司之间没有优先级别，货运公司只要满足他们的需求量就可以；货车完成他们日常的送货任务之后，回到港口。5) 假设运输车不会因天气状况，而影响其行驶速度，和装载、卸载时间。6) 运输路不会影响运输车行驶速度。7) 运输车正常出车。三、问题分析运输过程的最大特点是三种原料重量不同，分为大小件，当大小件同车，卸货时必须先卸小件，而且不允许卸下来的材料再装上车，要区别对待运输途中是否可以调头的费用。在问题一中，运输途中不能调头，整个送货路线是一个环形闭合回路，如果沿着某一方向同时给多家公司送货时，运输车必须为距离港口近的公司卸下小件，为距离港口远的公司运送大件；而在问
7、题二中，运输途中可以调头，可以首先为远处公司运送小件，在返回途中为距离较近的公司卸下大件。从表面上看， 这样运输能够节省车次，降低出车费用。但我们通过分析，在本题中，载重调头运输并不能降低费用。运费最小是货运公司调度运输车的目标，运费包括派车固定成本、从港口出车成本、载重费用和空载费用。建立模型时，要注意以下几方面的问题： 目标层：如果将调度车数、车次以及每车次的载重和卸货点都设为变量，模型中变量过多，不易求解。由于各辆运输车之间相互独立，可以将目标转化为两个阶段的求解过程，第一阶段是规划车次阶段，求解车次总数和每车次的装卸方案；第二阶段是车辆调度阶段，安排尽量少的车辆数，每车次尽量满载，使总
8、的运费最小。约束层：(1) 运输车可以从顺时针或者逆时针方向送货，要考虑不同方向时的载重用；(2) 大小件的卸车顺序要求不同原料搭配运输时，沿途必须有序卸货；(3) 每车次的送货量不能超过运输车的最大载重量；(4) 满足各公司当日需求。四、符号说明和名词约定符号含义单位备注S1(n)从港口到各个公司的货运最短里程集公里n=1、2、8；S2(n)卸载后返回港口的最短空载里程集公里n=1、2、8；Q(i)(n)n公司对货物i的实时需求量集单位/天n=1、2、8;i=A、B、C；W(j)(n)第j批运至第n公司货物的重量集吨n=1、2、8；j=1、2；Times(j)(n)第j批运至第n公司次数集次
9、n=1、2、8；j=1、2Yj(n)第j批运至第n公司的费用集元n=1、2、8；j=1、2；Y(d)第d问中组合运输的费用集元d=1、2、3；Charge(d)第d问中所有的运输费用集元d=1、2、3；TT(d)第d问中组合运输的耗时集小时d=1、2、3；Time(d)第d问中所有的运输耗时集小时d=1、2、3；五、建立模型一、问题一i. 车次规划模型的分析车次规划阶段只涉及到载重费用、空载费用和港口出车费用。运输途中不能掉头， 所以每车次都是沿闭合回路绕圈行驶。1) 运输途中不能掉头，所以为某些公司送货时，运输车从港口出发，按顺时针方向沿闭合回路绕行，为其它公司送货时，按逆时针方向沿闭合回路
10、绕行。公司和港口之间存在顺时针距离和逆时针距离，如下表：公司编号顺时针距离815242937454955逆时针距离524536312315115由表可知，运输过程中不可以掉头，为使得货运费用最低，我们按照问题分析中给出的最佳运输路径进行货物的分配运输。即若港口按顺时针和逆时针两个不同方向 出发，根据货运里程短，点为顺时针货运方向最远点，也是空载回港口的最近点， 根据货运里程短，点为逆时针货运方向最远点，也是空载回港口的最近点。结论：在符合载重相对最大化情况下，公司顺时针送货为最佳方案， 公司逆时针送货最佳方案。如下图所示：9公里 5公里8公里8公里7公里4公里港口8公里5公里6公里2）根据3种
11、原料的重量和运输车的最大运载量可以看出，A和C可以搭配运输，B和C可以搭配运输，而A与B不能同车运输。不论是以顺时针方向送货还是以逆时针方向送货，当大小件搭配运输时，必须首先卸下小件，在后续公司卸下大件。我们把这种特点总结如下：1、若在第j个公司卸下的是大件A，说明本车次的货物已经卸完，不能够再为后续 公司运送小件C（A与B不能同车运输，更不可能有B）；2、若在第j个公司卸下的是B，说明本车次的货物已经卸完，不能够再为后续公司 运送小件C。ii. 模型建立基于以上约束条件建立如下模型：第一步：根据车载重相对最大化的基本思想。可以分为两小步：分为两种满载方案：第1种为每个车次装载1单位A和2单位
12、C；第2种是每个车次装载2个单位B。并使每一车次在同一公司卸货。满载运载方案如下表1：表1车辆车次数公司货物时间（小时） 运费（元）各车工作时间（小时111A,2C1.4167107.27.083521A,2C1.4167107.232A,2C1.416718043A,2C1.4167273.653A,2C1.4167273.6264A,2C1.4167325.67.083575A,2C1.4167263.287A,2C1.4167138.497A,2C1.4167138.41022B1.416718031122B1.41671807.08351252B1.4167263.21362B1.41
13、671801462B1.41671801572B1.4167138.441682B1.416776）对于剩下各公司所需要货物单位数量如下表：材料A20020005B11010001C10002311第二步：我们采用批次运输方案：第一批次运输，我们使 A 材料有优先运输权， 在保证满足各公司对 A 需求量条件下，1C 与 1A 搭配满足载重相对最大化方法运输；第二批次运输，我们使 B 材料有优先运输权，在此次运输我们满足各公司尚缺 B 材料的量小于或等于 2 个单位；第三批次运输剩下所需的货物。具体运输方式：首先优先考虑 A 货物的处理方法，可知 1 公司还需 1 个车次的 1A 和一个车次的
14、1A1C，4 公司还需要 2 个车次的 1A，8 公司还需要 4 个车次的 1A 和 1 个车次的 1A1C；接着处理 B 货物，1 公司和 2 公司共需要 1 个车次的 2B,8 公司和 4 公司共需要 1 个车次的 2B;最后处理 C 货物，5、6、7 公司共需要 1 个车次的 6C。由此可知共出车 28 次。如下表 2：表 2车辆车次数公司货物时间（小时） 运费（元）各车工作时间（小时41682B1.4167767.0835178A,C1.416767188A1.416758198A1.416758208A1.4167585218A1.4167586.1334221A,C1.416792
15、.8231A1.416778.4241，22B1.5833142.26254A1.4167221.26.0333264A1.4167221.2277,6，56C1.75198.4288，42B1.5833206）2)根据 1）和 2）的结论及方法，不记派车成本和出车成本的 28 车次方案所需运费及时间如下表 3：表 3车辆车次数公司货物时间（小时）运费（元）各车工作时间（小时）111A,2C1.4167107.27.083521A,2C1.4167107.232A,2C1.416718043A,2C1.4167273.653A,2C1.4167273.6264A,2C1.4167325.67.
16、083575A,2C1.4167263.287A,2C1.4167138.497A,2C1.4167138.41022B1.416718031122B1.41671807.08351252B1.4167263.21362B1.41671801462B1.41671801572B1.4167138.441682B1.4167767.0835178A,C1.416767188A1.416758198A1.416758208A1.4167585218A1.4167585.8334221A,C1.416792.8231A1.416778.4241，22B1.5833142.26254A1.416722
17、1.26.1667264A1.4167221.2277，6，56C1.75198.4288，42B1.5833206总446440.5007模型中变量对应的数值含义S1(n)8 15 24 29 23 15 11从港口到各个公司的货运最短里程集5n=1、2、8；S2(n)52 45 36 31 37 45 49集卸载后返回港口的最短空载里程n=1、2、855；Q(i)(n)4 1 2 3 1 0 2 5；n公司对货物i的实时需求量集n=1、2、81 5 0 1 2 4 2 3；5 2 4 2 4 3 5 1i=A、B、C；Wj(n)21 6 12 14 6 012 21；第j批运至第n公司货物
18、的重量集n=1、2、8；j=1、2；0 1200 6 12 66Times(j)(n)4 1 2 3 1 0 2 5；第j批运至第n公司次数集n=1、2、80 2 0 0 1 2 1 1；j=1、2；(d)ttd=15.0832第d问中组合运输的耗时集)yd=1565.2第d问中组合运输的费用集iii. 目标分析运费最小是货运公司调度运输车的目标，运费包括派车固定成本、从港口出车成本、载重费用和空载费用。82ch arg e(d ) = Y(d ) + 1.8* S1(n) *W( j ) (n) + 0.4 * S 2(n)*times( j ) (n) +10 *times( j ) (n
19、);n=1 j =182time(d ) = TT(d ) + times( j ) (n)* (1+ 5 /12);其中d = 1；n=1j =1最后经过模型的计算得到最少费用为：4840.6元，最少耗时为：40.4999小时。二、 问题二i. 车次规划模型的分析两个定理的证明定理一、车辆当且仅当运完最后一件货物时才调头途中允许调头，运输车可以先为较远的公司送去小件原料，然后调头，为比较近的公司送去大件。从表面上看，这样运输能够节省车次，降低出车费用。但我们通过分析，在本题中，载重调头运输并不能降低费用。证明过程如下：NMS1S2O在上图中，记O点为港口，N、M为两公司。M到港口的距离是S1
20、，NM两个公司之间的距离为S2。假设将两种货物a和b（重量分别为x吨、y吨），分别运往N和M两公司，现有两种运输方案：1. 若先运货a、b到N，将a卸到N，调头返回，将货物b运往M，那么a必为C原料（x1），b为A或B（ 3 y 4 ），记运费用为f12. 若先单独运送货物a到N，返回港口后，再次出车，将货物b运往M，即出车两次，记运费用为f2。 两种方案需要的车辆相同时，为比较两种运输方式费用的大小，两种运输的种类质量均相同，记： f若f 0恒成立，则载重调头送货不节省费用，通过数据处理提取函数：= f1 - f2f = 3.6 y s2 -10 - 0.4(s1 + s2 )因为4 y 3
21、并且N、M两公司在本题中的最小距离s2 = 4代入到 f 中，化简得到fmin令fmin= 31.6 - 0.4s1= 31.6 - 0.4s1 75而港口到所有公司最短路的最大值为29公里，所以fmin 0 恒成立。说明前一种花费较高。 方案二比方案一需要的车辆多时第二种方案是出车两次，运输时间较长，在 8 小时的工作时间内，可能会比调头载重运输时多安排车辆，派车费用增加。我们考虑一种最差情况，因多运一次而增派一辆车，此时有fmin = 11.6 - 0.4s1 0得到s1 29因为港口到所有公司的最短路径所以s1 29fmin 0综上，载重调头运输花费较高。证明了以运费用最小为目标时，车辆
22、当且仅当运完最后一件货物时才调头。定理一的推论：运载里程与空载里程相同（表四中的第 28 车次例外），且每次出车均不绕圈工作。定理二、车辆载重行程是各公司到港口的最短路，且载重费用固定不变在定理一的基础上，车辆当且仅当运完最后一件货才调头，且每次出车均不绕圈工作，那么每一单位的原料都可以由最短路径运至需货公司。我们变换视角，从宏观的角度看去，对 8 个公司所需货物的数量分别乘以公司和港口的最短距离和载重单价（1.8 元/吨公里）就是将货物运至公司的载重费用，载重费用因子：货物的数量、公司和港口的最短距离、载重单价都是定值，因此，载重费用是固定不变的。车次规划阶段只涉及到载重费用、空载费用和港口
23、出车费用。运输途中可以掉头，即货车可以送完货沿原路返回港口。ii. 模型建立根据问题一约束条件：在符合载重相对最大化情况下，公司顺时针送货为最佳方案，公司逆时针送货最佳方案。此结论也可以适用货车可以掉头的情况。加上上面两个定理，数学模型与问题一几乎相同，只是空载路径不同。故同样分为两步骤：第一步分为两种满载方案：第1种为每个车次装载1单位A和2单位C；第2种是每个车次装载2个单位B。并使每一车次在同一公司卸货。第二步我们采用批次运输方案：第一批次运输，我们使A材料有优先运输权，在保证满足各公司对A需求量条件下，C与A搭配满足载重相对最大化方法运输；第二批次运输，我们使B材料有优先运输权，在此次
24、运输我们满足各公司尚缺B材料的量小于2个单位；第三批次运输剩下的货物。最终车次运载方案如下表 4：表 4车辆车次公司货物时间（小时）运费各车工作时间（小时）111A,2C0.683489.67.283721A,2C0.683489.632A,2C0.916716843A,2C1.2167268.853A,2C1.2167268.864A,2C1.3834324.875A,2C1.1834257.6287A,2C0.7834123.27.783897A,2C0.7834123.21022B0.91671681122B0.91671681252B1.1834257.61362B0.91671681
25、462B0.91671681572B0.7834123.21682B0.5834563178A,C0.5834474.2838188A0.583438198A0.583438208A0.583438218A0.583438221A,C0.683475.2231A0.683460.84241，22B1.0833130.26.9501254A1.3834220.4264A1.3834220.4277，6，52B1.5167192.8288，42B1.5833206总4127.226.3014iii. 目标分析运费最小是货运公司调度运输车的目标，运费包括派车固定成本、从港口出车成本、载重费用和空载费用。由表 4 得知，第二问的总费用 charge(2)=4127.2+20*4+10*28=4487.2 元总时间 Time(2)=26.3014 元三、 问题三1)第一小问：结论：这次运货不需要使用 4 吨货车。只使用 6 吨、8 吨货车搭配运输即可。i. 模型建立我们经过上述论证，排除了 4 吨货车的使用。题目没有规定车子不能变向，所以认为车辆可以掉头。我们仍旧采取公司顺时针送货，公司逆时针送货的方案。根据上述条件我们建模如下：第一步，使 8 吨车次满载并运往同一公司；第二步，使 6 吨位车次满载并运往同一公司； 运载方案如下表 5：表 5
