货车公司对货运车辆的调度问题

1、2008高教社杯全国大学生数学建模竞赛承 诺 书我们仔细阅读了中国大学生数学建模竞赛的竞赛规则.我们完全明白，在竞赛开始后参赛队员不能以任何方式（包括电话、电子邮件、网上咨询等）与队外的任何人（包括指导教师）研究、讨论与赛题有关的问题。我们知道，抄袭别人的成果是违反竞赛规则的, 如果引用别人的成果或其他公开的资料（包括网上查到的资料），必须按照规定的参考文献的表述方式在正文引用处和参考文献中明确列出。我们郑重承诺，严格遵守竞赛规则，以保证竞赛的公正、公平性。如有违反竞赛规则的行为，我们将受到严肃处理。我们参赛选择的题号是（从A/B/C/D中选择一项填写）： 我们的参赛报名号为（如果赛区设置报名

2、号的话）： 所属学校（请填写完整的全名）： 参赛队员 (打印并签名) ：1. 2. 3. 指导教师或指导教师组负责人 (打印并签名)： 日期： 年 月 日赛区评阅编号（由赛区组委会评阅前进行编号）：2008高教社杯全国大学生数学建模竞赛编 号 专 用 页赛区评阅编号（由赛区组委会评阅前进行编号）：赛区评阅记录（可供赛区评阅时使用）：评阅人评分备注全国统一编号（由赛区组委会送交全国前编号）：全国评阅编号（由全国组委会评阅前进行编号）货运公司对货运车辆的调度问题摘要写的非常好该题是一个车辆调度的最优化问题，因此是一个数学规划模型。问题一是在车型固定、车辆不能掉头、遵循货物不可拆分及卸货顺序的情况下

3、来进行货物运输，通过参照运筹学的数学规划模型理论，我们得出了在该情况下调用了6辆车，一共出车29次，得出最终运费为4886元，；问题二是在问题一的基础上增添了车辆可以中途掉头的条件，因此，卸空货物后原路返回港口以减少空载运费。我们得出了在该情况下调用了4辆车，一共出车29次，最终运费为4488.4元。问题三是增添了货车的类型下进行思考，这是分两种情况，第一种是在货车途中不可掉头的情况下进行讨论，则可参照问题一，可得调动了6吨、8吨的车，共出车23次，最终运费为4923.6元，。情况二是在货车中途可掉头，此时参照问题二，得出调用了6吨、8吨的车，共出车23次，最终运费为4548.8元。关键词：运

4、输费用 运输时间 lingo 0-1规划模型一、问题重述货运公司对货运车辆的调度问题 某地区有8个公司(如图一编号至)，某天某货运公司要派车将各公司所需的三种原材料A,B,C从某港口(编号)分别运往各个公司。路线是唯一的双向道路(如图)。货运公司现有一种载重 6吨的运输车，派车有固定成本20元/辆，从港口出车有固定成本为10元/车次(车辆每出动一次为一车次)。每辆车平均需要用15分钟的时间装车，到每个公司卸车时间平均为10分钟，运输车平均速度为60公里小时(不考虑塞车现象)，每日工作不超过8小时。运输车载重运费1.8元/吨公里，运输车空载费用0.4元/公里。一个单位的原材料A,B,C分别毛重4

5、吨、3吨、1吨，原材料不能拆分，为了安全，大小件同车时必须小件在上，大件在下。卸货时必须先卸小件，而且不允许卸下来的材料再装上车，另外必须要满足各公司当天的需求量(见表)。 问题： 1、货运公司派出运输车6辆，每辆车从港口出发(不定方向)后运输途中不允许掉头，应如何调度(每辆车的运载方案，运输成本)使得运费最小。 2、每辆车在运输途中可随时掉头，若要使得成本最小，货运公司怎么安排车辆数？应如何调度？3、(1)如果有载重量为4吨、6吨、8吨三种运输车，载重运费都是1.8元/吨公里，空载费用分别为0.2，0.4，0.7元/公里，其他费用一样，又如何安排车辆数和调度方案？(2)当各个公司间都有或者部

6、分有道路直接相通时，分析运输调度的难度所在，给出你的解决问题的想法(可结合实际情况深入分析)。图唯一的运输路线图和里程数公司材料A41231025B15012423C52424351 表各公司所需要的货物量二、基本假设1. 货车在运输途中没有抛锚。2. 工人的日工资固定的，不受上班时间的影响。3. 工人在装完货、卸完货后能立即出发。4. 港口能满足多车同时装货，无需排队等待。三、符号说明符号意义单位a派车数辆b出车次数辆j公司每天对A货的需求量吨j公司每天对B货的需求量吨j公司每天对B货的需求量吨第i趟车运到j公司的货物A数吨第i趟车运到j公司的货物B数吨第i趟车运到j公司的货物C数吨第i趟车

7、运货重量吨当=1，代表第i趟车运载货物A。当=0，代表第i趟车不运载货物A当=1，代表第i趟车运载货物B。当=0，代表第i趟车不运载货物B当=1，代表第i趟车运载货物C。当=0，代表第i趟车不运载货物C当=1，代表第i趟车用4吨的货车。当=0，代表第i趟车不用4吨的货车。当=1，代表第i趟车用6吨的货车。当=0，代表第i趟车不用6吨的货车。当=1，代表第i趟车用8吨的货车。当=0，代表第i趟车不用8吨的货车。第i趟车，货车从港口出发到j公司的距离公里四、问题分析本题根据货运公司所供车型吨位、所规定的运费、8个公司对三种原材料的需求量以及各公司之间路程关系，建立模型寻找最优方案，使得在满足各种限

8、制条件下运费最小化。三种原材料（重量不同）要求不能拆分，则三种货物运送时只能按整数个单位进行。放置顺序应满足大小件同车时必须小件在上，大件在下。卸货顺序必须先卸小件，而且不允许卸下来的材料再装上车，这样限制了卸货方式只有三种：在某一公司卸下全部货物在不同公司卸下同种货物在不同公司卸下不同货物，需满足小件在据港口近处的公司卸下，剩余货物在距离远处卸下。由于每日每辆车8小时的工作时间约束，每辆车应尽量满足最大载货量和充分利用工作时间。途中货车是否可以掉头按各个问题不同做了以下分析。问题一：由于车型固定，介于派车固定成本和出车固定成本，尽量减少出车次数，达到满载的四种运输方式：（a）6C、（b）B+

9、3C、（c）2B、（d）1A+2C。结合各公司所需减少装载的货物，并考虑到限制了运输途中不可掉头，则按各公司与港口间最短路程决定货车方向：顺时针方向往公司而公司应逆针方向出车，由此建立0-1模型。问题二：与问题一不同仅在于途中可以掉头，但为减少运费，不考虑将货物往回运，即问题一的方案中当货车卸空货物后原路返回港口，以较少空载路程和运送时间，可以增加每辆车出车次数，来达到降低运费。问题三：根据三种不同的货车的载运量、载重费用、空载费用，分为能否掉头两种情况进行讨论， 运往某公司的出车方向与问题一、二相同，并满足距离港口近的公司尽可能用大载运量货车，远距离运送用小载运量货车。可以掉头的情况则让货车

10、原路返回。二问中假设各个公司间都有或者部分有道路直接相通，根据问一指定的车辆运载分配方案，并选取距离短的路线运载目的地。五、模型的建立与求解5.1 问题一模型建立与求解5.1.1 问题一模型的建立目标函数分析：Min(所求的总费用)=总车辆的派车固定成本+出车固定成本+总运费约束条件分析：1） 货车载重量约束：货车载重量（6吨）所载A类货物重量+ 所载B类货物重量+ 所载C类货物重量2） 各公司需求量约束：A类货物需求量每趟去往该公司所载A类货物重量之和B类货物需求量每趟去往该公司所载B类货物重量之和C类货物需求量每趟去往该公司所载C类货物重量之和根据以上问题分析与限制条件，可列出以下目标函数

11、与方程组：5.1.2 问题一模型的求解运输方案见附录表格1，最终求得总运费为4886元，出车总次数为29次。5.1.3 问题一结果的分析及验证求解结果表明每辆车每天的工作均满足8小时时间限制，满足各公司每日各类货物的需求量，所求模型符合实际情况。5.2 问题二模型建立与求解5.2.1 问题二模型的建立在问题一的基础上，卸空货物后采用原路返回的方式，对问题进行求解。目标函数分析与条件约束分析与问题一一致。可列求解方程组如下：5.2.2 问题二模型的求解运输方案见附录表格2，最终求得总运费为4488.4元，出车总次数为29次。5.2.3 问题二结果的分析及验证求解结果表明每辆车每天的工作均满足8小

12、时时间限制，满足各公司每日各类货物的需求量，所求模型符合实际情况。5.3 问题三模型建立与求解 问题三模型的建立目标函数分析：Min(所求的总费用)=总车辆的派车固定成本+出车固定成本+总运费约束条件分析：3） 货车载重量约束：货车载重量（分别为8、6、4吨）所载A类货物重量+ 所载B类货物重量+ 所载C类货物重量4） 各公司需求量约束：A类货物需求量每趟去往该公司所载A类货物重量之和B类货物需求量每趟去往该公司所载B类货物重量之和C类货物需求量每趟去往该公司所载C类货物重量之和情况一（中途不可以掉头） 情况二（中途可以掉头）各个公司间都有或者部分有道路直接相通，根据问一指定的车辆运载分配方案

13、，并选取距离短的路线运载目的地。5.3.2 问题三模型的求解情况一：运输方案见附录表格3，最终求得总运费为4923.6元，出车总次数为26次。情况二：运输方案见附录表格4，最终求得总运费为4548.8元，出车总次数为26次。5.3.3 问题三结果的分析及验证求解结果表明每辆车每天的工作均满足8小时时间限制，满足各公司每日各类货物的需求量，但所求模型的总运费不满足最优化要求。六、模型的评价与推广7.1 模型的评价问题一、二的模型比较符合实际的要求。但问题三的模型未能达到最优7.2 模型的推广可运用于上班的人数安排。七、参考文献1 刁在筠等, 运筹学（第三版），高等教育出版社，2007年1月2 姜

14、启源等，数学模型（第四版），高等教育出版社，2011年1月八、附录 表一货车编号行驶方向次数公司编号载货方案载货时间/每人每天运费/每人每天总运费/每天1111A+2C435597.848861211A+2C1311A+1C1411A 151，21B+1B1121A+2C4251157.21222B1322B1431A+2C1531A+2C1141A+2C4251270.21241A 1341A 1441B0552B0151A+2C4259700262B0362B0472B0571A+2C0171A+2C445445025，6，72C，3C，1C0381A+1C0481A 0581A 0181

15、A 3403010281A 0382B0481B货车编号行驶方向次数公司编号载货方案载货时间/每人每天运费/每人每天总运费/每天1111A+2C448分1328.24488.41211A+2C1311A+1C1411A 151，21B+1B1621A+2C1722B1822B1931A+2C1131A+2C476分1540.21241A+2C1341A 1441A 1541B0652B0151A+2C413分12460262B0362B0472B0571A+2C0671A+2C075，6，72C，3C，1C0181A+1C2453740281A 0381A 0481A 0581A 0682B0

16、781B表二 表三货车编号行驶方向次数公司编号载货方案运费/每人每天总运费/每天111A+B+C1186.34923.6121A+4C1312A142、32A1522B+2C113A+4C1211.61242A0382A0482A058A+B+C017A+B+C792.5027A+B+C035A+B+C1122B10601222B134A+2C0482B056、76C0162B673.20000262B035B+3C 表四货车编号行驶方向次数公司编号载货方案运费/每人每天总运费/每天111A+B+C1064.54548.8121A+4C1312A142、32A1522B+2C113A+4C10

17、96.81242A0382A0482A058A+B+C017A+B+C729.5027A+B+C035A+B+C1122B1014.41222B134A+2C0482B056、76C0162B643.60262B035B+3C问题一1车：20+5*10+27*1.8*8+0.4*4*52+7*1.8*3+45*0.4= 597.80002车：20+5*10+18*1.8*15+0.4*3*45+12*24*1.8+2*0.4*36= 1.1572e+0033车：20+5*10+17*1.8*29+0.4*4*31+23*6*1.8+37*0.4= 1.2702e+0034车：20+5*10+6

18、*1.8*23+0.4*37+12*15*1.8+45*0.4*2+11*12*1.8+0.4*2*49=970.00005车：20+5*10+13*5*1.8+3*0.4*55+6*11*1.8+0.4*49+6*11*1.8+5*4*1.8+2*8*1.8+0.4*37= 589.80006车：20+4*10+17*5*1.8+4*0.4*55=301总运费：4886问题二1车：20+9*10+27*1.8*8+0.4*4*8+7*1.8*3+15*0.4+18*1.8*15+0.4*3*15+6*24*1.8+0.4*24= 1.3282e+0032车：20+6*10+6*24*1.8+

19、0.4*24+17*1.8*29+0.4*4*29+23*6*1.8+23*0.4= 1.5402e+0033车：20+7*10+6*1.8*23+0.4*23+12*15*1.8+15*0.4*2+11*12*1.8+0.4*2*11+6*11*1.8+0.4*11+6*11*1.8+5*4*1.8+2*8*1.8+0.4*23= 12464车：20+7*10+30*5*1.8+5*0.4*7= 374总运费：4.4884e+003（1车是1到9共448分，2车是10到15共476分，3车是16到22共413分，4车是23到29共245分）问题三情况一（不掉头）1车8吨：20+5*10+24*8*1.8+52*0.7*3+15*16*1.8+24*4*1.8+36*0.7+45*0.7= 1.1863e+0032车8吨：20+5*10+24*8*1.8+36*0.7+8*29*1.8+31*0.7+8*5*1.8*3+55*0.7*3= 1.2116e+003