乘用车物流运输计划

1、 第十一届华为杯全国研究生数学建模竞赛题 目 乘用车物流运输计划问题摘 要：本文针对如何制定总成本最低的装载运输方案，建立了3个模型分别解决在不同运输需求情况下，轿运车的装载运输方案。对于问题1、2和3，本文采用分步最优方法，第一步将轿运车分层讨论，建立单层轿运车最优装载的线性规划模型，求出每一类轿运车在不同乘用车装载组合方式中，使轿运车使用率最大的I型、II型和III型乘用车数量；第二步根据前一个模型求得的数据，建立最优装载方案模型，使得轿运车的总数量最少。利用MATLAB软件编程求解出3个问题所需轿运车的数量和每辆轿运车的详细装载方案。第1问需要16辆1-1型轿运车和2辆1-2型轿运车；第

2、2问需要12辆1-1型轿运车和1辆1-2型轿运车；第3问需要25辆1-1型轿运车和5辆1-2型轿运车。对于问题4，本文采用了两种方法求解。一种是人工调整运输方法，一种建模求解法。人工调整方法有两种方案，方案一是根据每个目的地需要的乘用车数量，利用最优装载方案模型求得单独对每点运输的轿运车数量，然后按照各点对乘用车的需求量调整轿运车的行驶路径和配送目的地，计算得到需要23辆1-1型轿运车和3辆1-2型轿运车。方案二是将全部目的地对I型和II型乘用车需求量当成一个整体，先对整体需求利用最佳装载模型求出装载这些乘用车的轿运车数量分别为21辆1-1型和4辆1-2型，然后再根据各目的地的需求安排配送。建

3、模求解法分为两步，第一步利用最优装载方案模型得到使用轿运车总数最少的装载方案：需要21辆1-1型和4辆1-2型轿运车。第二步在轿运车使用数量最少前提下，利用最优运输路径模型，采用遗传算法对25辆轿运车进行路径规划，保证所有轿运车行驶的总路程最短。对于问题5，本文首先将其转化为三维装箱问题建立最优装载方案模型，采用遗传算法求出最优解，使轿运车使用数量最少，结果为126辆轿运车。利用问题4中建立的最优运输路径模型规划所有轿运车的行驶路径。关键词：最优装载方案模型；最优运输路径模型；遗传算法；三维装箱1 问题重述整车物流指的是按照客户订单对整车快速配送的全过程。根据用户订单的要求，物流公司制定运输计

4、划并配送乘用车。先选出可调用的轿运车，然后再给出其中每一辆轿运车中乘用车的装载方法和目的地。根据型号的不同，本题中轿运车有三种车型：上下层各装载1列乘用车，记为1-1型；下、上层分别装载1、2列，记为1-2型；上、下层各装载2列，记为2-2型，每辆轿运车可以装载乘用车的最大数量在6到27辆之间。影响成本高低的首先是轿运车使用数量；其次，在轿运车使用数量相同情况下，1-1型轿运车的使用成本较低，2-2型较高，1-2型略低于前两者的平均值，但物流公司1-2型轿运车拥有量小，为方便后续任务安排，每次1-2型轿运车使用量不超过1-1型轿运车使用量的20%；再次，在轿运车使用数量及型号均相同情况下，行驶

5、里程短的成本低。轿运车到达目的地后原地待命，无须放空返回。最后每次卸车成本几乎可以忽略。每种轿运车上、下层装载区域均可等价看成长方形，各列乘用车均纵向摆放，相邻乘用车之间纵向及横向的安全车距均至少为0.1米，下层力争装满，上层两列力求对称，以保证轿运车行驶平稳。受层高限制，高度超过1.7米的乘用车只能装在1-1、1-2型下层。轿运车、乘用车规格（第五问见附件）如表1和表2所示。表1乘用车规格乘用车型号长度(米)宽度(米)高度(米)4.611.71.513.6151.6051.3944.631.7851.77表2轿运车规格轿运车类型上下层长度(米)上层宽度(米)下层宽度(米)1-1192.72.

6、71-224.33.52.7依据以上要求为物流公司安排以下五次运输制定详细计划，含所需要各种类型轿运车的数量、每辆轿运车的乘用车装载方案、行车路线：（1）物流公司要运输车型的乘用车100辆及车型的乘用车68辆。（2）物流公司要运输车型的乘用车72辆及车型的乘用车52辆。（3）物流公司要运输车型的乘用车156辆、车型的乘用车102辆及车型的乘用车39辆。（4）物流公司要运输166辆车型的乘用车（其中目的地是A、B、C、D的分别为42、50、33、41辆）和78辆车型的乘用车（其中目的地是A、C的，分别为31、47辆），具体路线如图1所示，各段长度：OD=160，DC=76，DA=200，DB=1

7、20，BE=104，AE=60。EBACDO图1 路线图 （5）附件的表1给出了物流公司需要运输的乘用车类型（含序号)、尺寸大小、数量和目的地，附件的表2给出可以调用的轿运车类型（含序号)、数量和装载区域大小（表里数据是下层装载区域的长和宽, 1-1型及2-2型轿运车上、下层装载区域相同；1-2型轿运车上、下层装载区域长度相同，但上层比下层宽0.8米。此外2-2型轿运车因为层高较低，上、下层均不能装载高度超过1.7米的乘用车。 2 问题分析对于问题1、2、3，由于运输过程中的目的地只有一个，故可以暂时不讨论行车路线对运输方案的影响，只需在乘用车数量被限定的情况下，找出使轿运车车使用率最大的车辆

8、分配方案。首先考虑到轿运车具有两层结构，而高于1.7m的乘用车只能装载在轿运车的下层，故而1-1型和1-2型轿运车的上层只能装载I型和II型乘用车，因此在混合装载时轿运车上层和下层的混合方式不完全相同，必须将轿运车进行分层研究，分别找到每一层中使轿运车的使用率达到最大的最优组合方式。其次，确定了对轿运车进行分层寻优的方案后，在宽度和高度的限制达到要求的情况下，可以将这一层中所有乘用车总长度最大作为目标问题的判断标准。可以使用线性规划的方法单独对每一层中的不同乘用车组成形式做线性计算，由此可以得到一个关于每种组合的每一种轿运车的每一层中分别含有的I、II、III型乘用车的数量表格。最后，根据该数

9、量表格中对每一层不同组合下的I、II、III型乘用车的数量，以及问题1、2、3对于车型和数量的不同要求作为约束条件，建立线性规划模型，求解出满足题目运输要求的1-1型和1-2型轿运车的数量。对于问题4，由于运输过程中的目的地变成了4个，则行车路线对成本的影响较大。如果按照人的经验分配和从可行结果的多样性角度进行装载方案的分配，可以得到不同的解。所以可以先考虑按每个目的地对乘用车的需求去分配装载轿运车，也可根据先用最少的轿运车转载全部运输需求的乘用车，然后进行人工调整。只需要考虑运输I型和II型两种乘用车，就不需要因为考虑到III型乘用车只能放在轿运车下层而将轿运车上下两层分开求出最优组合分配后

10、在对各层组合。如果仍按照模型I中对轿运车每一层分别求组合比，再对上、下层不同装载方式进行组合，这样每一辆轿运车中能够装载的I型和II型轿运车的装载比就有很多种可能。为了减少这种多组合的可能，将模型I中原本按照上、下层组合分配的方式改为根据整车装载最优重新进行分配。再根据得到的最优装载方案建立一个以行驶总路程最短的模型，可按照从整体需求求解最优运输方案，此时就可以利用遗传算法对行驶的最短路径求解。对于问题5，要求根据附件表1和附件表2中提供的有限的10种轿运车对5个目的地配送45种乘用车。每个目的地对各种乘用车的需求量不同。由于附件表中提供的车型数量较多，如果依照前面的模型建立方法对最少轿运车使

11、用数量进行研究，一方面系数矩阵很大，另一方面这种系数矩阵需要手动整理，这样不利于编程和结果的输出。于是可建立一个新的三维装箱模型对最少轿运车数量求解，最终利用问题4的模型和遗传算法对最优运输方案进行优化求解。3 模型假设1、假设在有两列的1-2型和2-2型轿运车中，装载乘用车时左右两列是对称的；2、假设在轿运车装载乘用车时，不考虑乘用车与轿用车车壁间的距离；3、假设1-1型轿用车的运输成本为1。4 符号说明符号说明在轿用车单列第种乘用车的数量第种乘用车的长度乘用车的总长度第种轿运车的长度1-1型轿运车总数1-2型轿运车总数在第层中的第种组合的1-1型轿运车数量在第层中的第种组合的1-2型轿运车

12、数量2-2型的运行成本1-1型轿运车装载第型乘用车总数量的系数矩阵第种组合的1-1型轿运车系数1-2型轿运车所装载的型乘用车总数的系数矩阵第种组合的1-2型轿运车系数以第种组合方式装载的1-1型轿运车层数以第种组合方式装载的1-2型轿运车层数第种乘用车的需求量矩阵所有轿运车行驶的总路程5 问题1、2、3的模型建立与求解5.1 最优装载方案模型的建立通过对轿运车中装载乘用车的高度和宽度的限制可以知道，各车型的宽度在组合中只有I型和III型的不能并列放置，而又有层高高于1.7m的乘用车只能放在轿运车的下层的要求，那么III型车只能放在下层，所以不用考虑轿运车的宽度和高度对乘用车组合的限制。因为II

13、I型乘用车只能放在1-1型和1-2型的下层，又因为1-2型轿运车的上层有两列，为了让每一层中的每一列都能达到最大的使用率，可以把每一种轿运车分为上下两层，每一层中的乘用车就有不同的组合形式，组合方案如表3所示。表3 乘用车各层组合方案1-1下层I型II型III型I型和II型I型和III型II型和III型I型、II型和III型1-1上层I型II型I型和II型1-2下层I型II型III型I型和II型I型和III型II型和III型I型、II型和III型1-2上层I型II型I型和II型由此便得到每一层的组合形式分别为：1-1型下层7种，1-1型上层3种；1-2型下层7种，1-2型下层3种。假设要使得轿

14、运车的使用率达到最大（即装载的车辆最多），就要使得乘用车中上下两层每一列的总长度达到最大。因此只要分别得出每一层里面每一种组合方式中使轿运车的使用率达到最大的车辆数，就可以使得每一种乘用车组合在每一种轿运车的一层中达到最大使用率。5.1.1各乘用车组合在轿运车单层中的最优装载方案由于要求1-2型轿运车的上层两列力求对称，以保证轿运车行驶平稳，那么只需要考虑单列的最优数量即可。于是首先建立一个线性规划模型，求出在每一层的单列中，每种组合情况下个型号乘用车的数量。因为在每一层中有不同的组合模式，故可设置一个0-1函数，即：又假设各组合中第种乘用车的数量为，第种乘用车的长度为，则在一列的组合中，乘用

15、车的总长度为 显然只要使每一种组合中单列乘用车的总长度达到最大即可，于是可得目标函数为 而每一种轿运车的长度有限制，且每两辆乘用车间至少间隔0.1m，则在轿运车的一列中就有约束条件其中表示第种轿运车的长度。根据实际情况组合的不同，可知在各组合中每一种乘用车的数量为不为0的正整数。于是得到在不同组合形态下，每一辆轿运车单层单列的最多能放置组合乘用车数量的线性规划模型 （1）由表1和表2可知各型号乘用车和轿运车的长度和。根据组合模型中各种乘用车的数量，利用LINGO软件求解出使轿运车的利用率最大时各列组合中乘用车的数量。但是1-2型轿运车上层是对称的，故1-2型轿运车上层各乘用车数量应为其结果的两

16、倍。最后每一层中各组合情况下使轿运车达到最大利用率的乘用车数量结果如表4所示。表4 单层每种组合达到最大利用率的乘用车数量组合形式I型（1）II型（2）III型（3）I型和II型（4）I型和III型（5）II型和III型（6）I型、II型和III型（7）1-1下层（1）I4311II5111III43321-1上层（2）I43II511-2下层（1）I5211II6444III54211-2上层（2）I104II128注：表中“”表示组合中没有该种型号的乘用车。5.1.2 轿运车总量最小的最优装载方案模型 针对问题1，现假设1-1型轿运车有辆，1-2型轿运车有辆。要得到最佳的装载方案，只需轿运

17、车的使用量尽量少，即可将轿运车总数量的最小值作为目标函数，即目前， I型乘用车有100辆的同时II型乘用车有68辆，故而通过表4可得两种轿运车上、下层含有I型和II型乘用车的组合形式各乘用车数量。由此可以得到全部含有I型和II型乘用车组合中I型乘用车达到单层最大利用率的数量即如表5所示。表5 含有I型乘用车的组合形式下各层乘用车数量I组合形式I型（1）I型和II型（4）1-1下层（1）431-1上层（2）431-2下层（1）521-2上层（2）104同样，我们可以得到全部含有I型和II型乘用车组合中II型乘用车达到单层最大利用率的数量即如表6所示。表6 含有II型乘用车的组合形式下各层乘用车数

18、量II组合形式II型（2）I型和II型（4）1-1下层（1）511-1上层（2）511-2下层（1）641-2上层（2）128设表示在第层中的第种组合的1-1型轿运车数量；表示在第层中的第种组合的1-2型轿运车数量。根据I型乘用车有100辆的条件，结合表5可得约束条件同样，根据II型乘用车有68辆的条件结合表6可得约束条件又因为每种轿运车上下两层的层数应当相同，且每一种轿运车单层总数与总车辆数相等，所以物流公司1-2型轿运车拥有量小，为方便后续任务安排，每次1-2型轿运车使用量不超过1-1型轿运车使用量的20%，则有综上，可以得到使得总的轿运车数量最小的线性规划模型 （2）使用MATLAB软件

19、编程（程序见附录1）求解该模型可得到总共最少需要18辆轿运车。此时可以得到1-1型乘用车15辆，1-2型乘用车3辆。5.1.3运输成本最小的最优装载方案模型关于成本的计算中，首先考虑轿运车总数越少越好，但是在轿运车数量相同的情况下，就应当考虑1-1型和1-2型轿运车的运输成本。因为我们是以最少总数作为目标函数的，但实际情况是1-2型轿运车的运行成本相对1-1型轿运车的运行成本是比较大的，所以，在得到最少的总轿运车数量的前提下，还应当考虑到运行成本的总数最少。 （1）针对问题1，由于1-1型轿运车的使用成本较低，2-2型较高，1-2型略低于前两者的平均值，我们假设2-2型的运行成本是1-1型的倍

20、，即假设1-1型轿运车的运行成本为1，则1-2型轿运车的运行成本略小于；因为的取值必然是大于1的，所以我们可以得到1-2型轿运车的运行成本大于1。我们假设1-2型轿运车的运行成本为1.2，然后修改式（2）中的目标函数得到运行成本最少的目标函数为在改进的模型下，我们可以得到具体关于1-1型和1-2型乘用车在总的使用数量相同的情况下，分配比例为1-1型16辆，1-2型2辆。此时，由程序结果可以得到这18辆车的装载组合形式为（具体见表7）：1）7辆1-1型轿运车全部装载I型乘用车，共装载56辆I型乘用车；2）7辆1-1型轿运车上层全部装载I型乘用车，下层全部装载II型乘用车，共装载28辆I型乘用车和

21、35辆II型乘用车；3）2辆1-1型轿运车上层全部装载II型乘用车，下层全部装载I型和II型乘用车，共装载6辆I型乘用车，12辆II型乘用车；4） 又因为要求下层尽量装满，优先装载下层，则2辆1-2型轿运车下层全部装载I型和II型乘用车的组合模式，共4辆I型乘用车和8辆II型乘用车；按要求还需放置6辆I型和13辆II型乘用车在上层。2辆1-2型轿运车装载10辆I型和21辆II型乘用车。表7 轿运车分配方案问题1组合方案装载比数量总数上层下层IIIIII1-1型II8 07560III4 5728 35III&II3626121-2型I&III&II6 12210 21实际需要的I型和II型乘用

22、车的数量10068满载情况下I型和II型乘用车的数量102 71 至此，100辆I车型的乘用车和68辆II车型的乘用车全部装载完毕。（2）针对问题2，现假设有X辆1-1型轿运车，有Y辆1-2型轿运车。与问题1相同，得到运行成本最少的目标函数为目前， II型乘用车有72辆的同时III型乘用车有52辆，故而通过表4可得在两种轿运车上、下层含有II型和III型乘用车的组合形式各乘用车数量。由此可以得到全部含有II型和III型乘用车组合中II型乘用车达到单层最大利用率的数量即如表8所示。表8 含有II型乘用车的组合形式下各层乘用车数量II组合形式II型(2)II型和III型(6)1-1下层（1）511

23、-1上层（2）501-2下层（1）641-2上层（2）120 同样，我们可以得到全部含有I型和II型乘用车组合中II型乘用车达到单层最大利用率的数量即如表9所示。表9含有III型乘用车的组合形式下各层乘用车数量III组合形式III型(3)II型和III型(6)1-1下层（1）431-1上层（2）001-2下层（1）521-2上层（2）00根据II型乘用车有72辆的条件，结合表7可得约束条件同样，根据III型乘用车有52辆的条件结合表8可得约束条件与问题1相同，综上可以得到一个使得运行成本最少的线性规划模型 （3）使用MATLAB软件编程求解该模型可得到总共最少需要13辆轿运车。我们可以得到具体

24、的分配比例为，1-1型12辆，1-2型1辆。此时，由程序结果可以得到这13辆轿运车的装载组合形式为（具体见表10）：1）12辆1-1型轿运车上层全部装载II型乘用车，下层全部装载III型乘用车，共装载60辆II型乘用车和48辆III型乘用车；2）1辆1-2型轿运车上层全部装载II型乘用车，共12辆II型乘用车，下层装载III型乘用车，共4辆。表10 轿运车分配方案问题2组合方案装载比数量总数上层下层IIIIIIIIII1-1型IIIII5 41260481-2型IIIII12 5112 4实际需要的II型和III型乘用车的数量7252满载情况下II型和III型乘用车的数量72 53 至此，72

25、辆II车型的乘用车和52辆III车型的乘用车全部装载完毕。（3）针对问题3，假设有X辆1-1型轿运车，有Y辆1-2型轿运车。与问题1和问题2相同，得到运行成本最少的目标函数为目前， I型乘用车有156辆、II型乘用车102辆及III型乘用车39辆，故而通过表4可得在两种轿运车上、下层含有I型、II型和III型乘用车的组合形式各乘用车数量。由此可以得到全部含有I型、II型和III型乘用车组合中各类型乘用车达到单层最大利用率的数量即如表11所示。 表11 含有I、II、III型乘用车的组合形式下各层乘用车数量I组合形式I型（1）I型和II型（4）I型和III型（5）I型、II型和III型（7）1-

26、1下层（1）43111-1上层（2）43001-2下层（1）52111-2上层（2）10400II组合形式II型（2）I型和II型（4）II型和III型（6）I型、II型和III型（7）1-1下层（1）51111-1上层（2）51001-2下层（1）64441-2上层（2）12800III组合形式III型（3）I型和III型（5）II型和III型（6）I型、II型和III型（7）1-1下层（1）43321-1上层（2）00001-2下层（1）54211-2上层（2）0000根据I型乘用车有156辆、II型乘用车有102辆及III型乘用车有39辆的条件，结合表9可以得到约束条件与问题1和2相同，

27、综上可以得到运行成本最少的线性规划模型（4）使用MATLAB软件求解上述模型可得到总共最少需要30辆轿运车。我们可以得到具体的分配比例为，1-1型25辆，1-2型5辆。此时，由程序结果可以得到这19辆轿运车的装载组合形式为（具体见表12）：1）7辆1-1型轿运车全部装载I型乘用车，共装载56辆I型乘用车；2）10辆1-1型轿运车上层全部装载I型乘用车，下层全部装载II型乘用车，共装载40辆I型乘用车，50辆II型乘用车。3）7辆1-1型轿运车上层全部装载I型乘用车，下层全部装载III型乘用车，共装载28辆I型乘用车，28辆III型乘用车。4）1辆1-1型轿运车上层全部装载I型乘用车，下层装载I

28、型和III型组合形式的乘用车，共装载5辆I型乘用车，3辆III型乘用车。5）3辆1-2型轿运车上下层都装载I型和II型组合形式的乘用车，共装载18辆I型乘用车，36辆II型乘用车。6）2辆1-2型轿运车上层装载I型和II型组合形式的乘用车，下层装载I型和III型组合形式的乘用车，共装载9辆I型乘用车，16辆II型乘用车，4辆III型乘用车。表12 轿运车分配方案问题3组合方案装载比数量总数上层下层IIIIIIIIIIII1-1型II8 0075600III4 501040 500IIII404728028II&III50315031-2型I&III&II6 120318 360I&III&II

29、I58429168实际需要的I型、II型和III型乘用车的数量15610239满载情况下I型、II型和III型乘用车的数量15710239至此，156辆I车型的乘用车、102辆II车型的乘用车及39辆III车型的乘用车全部装完。5.2 最优装载方案的通用模型通过对装载方案的模型推导的过程和对第3问的以及求解过程可以将配置最佳装载形式的模型进行推广，使在任意运输的乘用车型号和数量的情况下，都能够直接根据通用模型得到最佳的分配方案。表13 各乘用车车型在各层各组合中的数量组合12345678910I1-140031014031-250021011004II1-105010110511-206040

30、440128III1-100403320501-20050421000事实上，每一种乘用车数量的约束条件中轿运车数量前的系数都是由表9中3种乘用车车型在不同组合的数量得到的；约束条件中总乘用车车辆的组成是由每种轿运车上下层装载乘用车的数量结合而来的。然而，在每一种轿运车中，上层实际上只有3种组合方式，所以，可以把上下层结合起来，看做乘用车只有10种组合方式，于是可以得到各乘用车车型在各层各组合中的数量如表13所示。不妨用表示1-1型轿运车装载第型乘用车总数量的系数矩阵。表示第种组合的1-1型轿运车系数。例如表10中阴影部分的表示1-1型轿运车所装载的I型乘用车总数的系数矩阵，即 同理可用表示1

31、-2型轿运车所装载的型乘用车总数的系数矩阵。表示第种组合的1-2型轿运车系数。设表示以第种组合方式装载的1-1型轿运车层数；设，表示以第种组合方式装载的1-2型轿运车层数。则表示所有1-1型轿运车使用的总量；表示所有1-2型轿运车使用的总量。令矩阵，综上所述可以得到装载方案的通用模型为 （5）其中表示第种乘用车的需求量矩阵。利用MATLAB程序（见附录2），我们可以得到使用该模型计算出的结果与前面所求得的结果一致，故该通用模型符合我们所要达到的规划目标。6 问题4的模型建立与求解6.1 最优装载方案6.1.1 人工调整方案一针对问题4，只需要将166辆I型和78辆II型乘用车运输到A、B、C、

32、D四个目的地，故可以暂时不考虑E点对于本题模型建立的影响。则实际运输路线图如图2所示，其中，。题目中给出了需要运输到A、B、C、D四个目的地的I型和II型乘用车的数量，其中目的地是A点需要42辆I型和31辆II型乘用车；B点需要50辆I型乘用车；C点需要33辆I型和47辆II型乘用车；D点需要41辆I型乘用车。图2 运输路线图如果单独对某一个点运输该目的地所需要的I型和II型车，而不考虑中途路过某地卸载乘用车的情况，由前三问的模型可以求得运送42辆I型和31辆II型乘用车到A点需要的轿运车各车型的数量、上下层的组合方案如表14所示。表14 运送到A点的轿运车分配方案A点组合方案装载比数量总数上

33、层下层IIIIII1-1型II8 03240III4 5416 201-2型III&II2 1612 16满载情况下I型和II型乘用车的数量42 36A点实际需要的I型和II型乘用车的数量4231由表14可知，在这种运输分配方案中，总共使用了7辆1-1型轿运车，1辆1-2型轿运车；装载比表示，在该型号轿运车中按照对应的组合方案装载乘用车时，装载的I型乘用车和II型乘用车的比例关系。由此可以计算出所有轿运车满载时可装载42辆I型乘用车和36辆II型乘用车。这个数量比题目要求的运输到A点的42辆I型和31辆II型乘用车要多出装载5辆II型乘用车的车位，即一辆装载了II型乘用车的轿运车没有装满。由组

34、合方案可知，要么减少1辆1-1型轿运车，要么减少1辆1-2型轿运车，其他的全部满载。这时，减少前者使得满载轿运车运输了38辆I型乘用车，31辆II型轿运车，还缺少4辆I型乘用车；减少后者使得满载轿运车运输了40辆I型乘用车，20辆II型轿运车，即还缺少2辆I型和11辆II型。同理得到如表15所示的运送50辆I型乘用车到B点需要的轿运车内部装载比例。表15 运送到B点的轿运车分配方案B点组合方案装载比数量总数上层下层IIIIII1-1型II8 054001-2型II15 0115 0满载情况下I型和II型乘用车的数量55 0B点实际需要的I型和II型乘用车的数量500从表15可以知道，在这种运输

35、分配方案中，总共使用了5辆1-1型轿运车，1辆1-2型轿运车。由此可以计算出所有轿运车满载时可装载55辆I型乘用车。这个数量比题目要求的运输到B点的50辆I型乘用车要多出装载5辆I型乘用车的车位，即一辆装载了I型乘用车的轿运车没有装满。由组合方案可知，要么减少1辆1-1型轿运车，要么减少1辆1-2型轿运车，其他的全部满载。这时，减少前者使得满载轿运车运输了47辆I型乘用车，即还缺少3辆I型乘用车；减少后者使得满载轿运车运输了40辆I型乘用车，即还缺少10辆I型乘用车。综上，同样可以得到如表16所示的C点和D点的运输方案。表16 运送到C点D点的轿运车分配方案C点组合方案装载比数量总数上层下层I

36、IIIII1-1型III4 5728 351-2型I&III&II6 1216 12满载情况下I型和II型乘用车的数量34 47C点实际需要的I型和II型乘用车的数量3347D点组合方案装载比数量总数上层下层IIIIII1-1型II8 06480满载情况下I型和II型乘用车的数量48 0D点实际需要的I型和II型乘用车的数量410同样，从表16可以知道，C点总共使用了7辆1-1型轿运车，1辆1-2型轿运车；D点总共使用了6辆I型轿运车。结果满载时都比实际需要的数量多出了一些。C点中减少1辆1-1型轿运车使得满载轿运车运输了30辆I型乘用车和42辆乘用车，即还缺少3辆I型乘用车和5辆II型轿运车

37、；D点中减少1辆1-1型的轿运车使得满载轿运车运输了40辆I型乘用车，即还缺少1辆I型乘用车。综合上面的结果，可以知道，当D点减少1辆1-1型轿运车时，D点值缺少1辆I型乘用车，而C点的分配方案中恰好多出了一辆I型乘用车；而A点减少一辆1-1型上I下II组合的轿运车时，II型乘用车刚好能够满足需求，而I型乘用车缺4辆，可以发现，B中的I型乘用车刚好多出了5辆。于是有以下第一种方案：第一步，使用3辆上I下I和3辆上I下II的1-1型轿运车和1辆1-2型轿运车运送乘用车去A点；4辆1-1型和1辆1-2型轿运车去B点；6辆1-1型和1辆1-2型轿运车去C点；5辆1-1型轿运车去D点。第二步，将1辆上

38、I下II组合的1-1型轿运车从O点发出，路径D点时卸下1辆I型乘用车，其余的全部运往C点。这样运送完C点和D点需求所需要的轿运车总数为12辆。第三步，将1辆装载有7辆I型乘用车的1-1型轿运车从O点发出，路径B点卸下3辆I型乘用车，然后将剩余的4辆I型乘用车运送到A点。这样分配使得所有到达目的地满载的轿运车总数都是最少的，余下作为补充的中途有停靠的轿运车的路线也是相对简单的路线。最后总共使用了23辆1-1型轿运车和3辆1-2型轿运车。具体的分配方案I如表17所示。表17 人工调整方案一组合方案直达目的地轿运车数量上层下层ABCD1-1型II3405III30601-2型II0100I&III&

39、II0010III&II1000非直达组合方案轿运车数量装载情况停靠点卸载数量到达点卸载数量上层下层IIIIIIIII1-1型II170B30A40III145D10C356.1.2 人工调整方案二当我们不考虑目的地，将满足总体运输要求且以轿运车数量最少作为首要目标时，则可根据前文的装载组合方案确定每种轿运车数量，及每辆轿运车装载I、II型乘用车的具体数量。根据前3问求解结果，可以知道整个运输方案至多有一辆车没有装满。使用MATLAB程序，利用问题123的模型，可算出166辆I型和78辆II型乘用车最少要21辆1-1型、4辆1-2型轿运车才能全部运输。这25辆车的具体装载方案如表18所示。表1

40、8 不考虑目的地的装载方案上层下层装载比数量总数IIIIII1-1型II8 0151200III4 5624 301-2型I&III&II6 12424 48满载情况下I型和II型乘用车的数量168 78 在各类轿运车数量之和固定的情况下，考虑如何将乘用车按要求运输到各点时，所有轿运车行驶的路程之和最短。为达到这个目标，就是在距离O点近的点尽可能的卸空更多的车，即运输是由近及远的。结合模型I，尽量让这25辆车按照A、B、C、D各点运输需求作为目标时的情况运输，根据表14至表16，因为D距离O点最近，优先分配D的需求，D原本至少需要以I上I下装载的1-1型轿运车6辆（其中5辆满，1辆有空位），则

41、让5辆以I上I下装载的1-1型轿运车直接去D，此时D缺1辆I型乘用车。同理，C距离O点第二近，则6辆以I上II下放置的1-1型轿运车全部去C，1辆上下都装载了I和II的1-2型轿运车去C，此时C缺3辆I型乘用车车，5辆II型乘用车；B点分配5辆I上I下装载的1-1型轿运车，此时B缺10辆I型乘用车；A点分配3辆以I上I下装载的1-1型车，此时A缺18辆I型和31辆II型乘用车。此时，O点只剩2辆以I上I下装载的1-1型轿运车，3辆上下都装载I型和II型乘用车的1-2型轿运车。这5辆轿运车最多可以装载34辆I型和36辆II型乘用车。而A、B、C、D四个目标点需要补充32辆I型和36辆II型乘用车

42、。表19 O点轿运车变化情况上层下层装载比数量送往目的点后剩余IIIDCBA1-1型II8 015101052III4 5660001-2型I&III&II6 1244333表20 各目的地缺少各型号乘用车数量ABCDI181031II31050接下来，需要确定对各目的地补充运输的方案。四个目的地只有A、C需要补运II型乘用车，并且补运数量是36辆，则在O点剩下的轿运车中只有3辆上下都装载I型和II型乘用车的1-2型轿运车可运输II型乘用车，且恰好可以装载36辆II型乘用车，则这3辆1-2型轿运车必然停靠在A或C点上。C点是岔路上的点，而C同时缺I型和II型乘用车，则在O点剩余的轿运车装载组合

43、中，必须选取且只用选取1辆1-2型轿运车对C点补运。这辆轿运车途径D点，且满足C点补充要求后还有多余的空间装载其他乘用车。但如果只装C、D点所缺乘用车的数量，O点其他4辆轿运车就装不下B、A所缺的各类型乘用车数量，所以这辆车必然要返回到D后向B配送。D、C补运完成后，2辆只装I型乘用车的1-1型轿用车只用对B、A补运，仍然需要在较近的B点尽可能的卸空更多的轿运车。综上，3辆1-2型轿运车最后都在A点完成卸载，空车待命。2辆1-1型轿运车直达B点，1辆卸完，空车待命，1辆去往A点。具体分配方案见表21。表21 人工调整方案二直达组合方案直达目的地轿运车数量上层下层ABCD1-1型II3505II

44、I00601-2型I&III&II0010非直达组合方案轿运车数装载卸载数量卸载数量卸载数量上层下层III停靠III停靠III终点III1-1型II180B801-1型II180A801-2型I&III&II1412D10C35A071-2型I&III&II1612B20A4121-2型I&III&II1612A6126.1.3 两种人工调整方案的比较 对比最优运输装载方案I和II： （1）在运载总数上方案I要比方案II多1辆轿运车。如果乘用车数量的多少决定成本大小的比重较大，那么方案II相对优于方案I。 （2）在轿运车型号分配上，方案I需要23辆1-1型轿运车，3辆2-2型轿运车，方案II需

45、要21辆1-1型轿运车，4辆2-2型轿运车，如果1-1型和1-2型轿运车在运输成本上差价较大，那么选择方案I略优于方案II。 （3）如果考虑到所有轿运车行驶的路径和距离，方案I总共行驶了6168,方案II总共行驶了6652。则在行驶距离越短越好的情况下，方案I优于方案II。6.2最优运输路径6.2.1 装载方案模型的简化由于在第4问中只需要考虑运输I型和II型两种乘用车，就不需要因为考虑到III型乘用车只能放在轿运车下层而将轿运车上下两层分开求出最优组合分配后在对各层组合。如果仍按照模型I中对轿运车每一层分别求组合比，再对上、下层不同装载方式进行组合，这样每一辆轿运车中能够装载的I型和II型轿

46、运车的装载比就有很多种可能。为了减少这种多组合的可能，将模型I中原本按照上、下层组合分配的方式改为根据整车装载最优重新进行分配。由前面求解过程可知，只需要改变模型I中的系数矩阵，就可以得到以整辆轿运车装载各种组合乘用车形式，求解不考虑目的地且满足目的地需求,得到分别满足A、B、C、D四目的地对I型和II型乘用车需求的最少乘用车数。改用整车计算轿运车最大占用率下各组合中各乘用车数量，即将表4简化为表22即可，这样就不用考虑上下层组合的问题。表22 每种组合达到最大利用率的乘用车数量组合形式I型II型I型和II型1-1型I804II01051-2型I1506II01812将表22转变为每种型号乘用

47、车在不同组合形式下数量的系数表23。表23 系数表I型（1）II型（2）I型和II型（3）I1-18041-21506II1-101051-201812例如模型I中的系数矩阵变为根据新的系数矩阵，利用模型I求解出满足各目的地对各乘用车数量需求的分配方案。与方案II相似的，然后根据这个分配方案，可以计算出满足166辆I型乘用车和78辆II型乘用车运输需求的轿运车数量。分别为21辆1-1型轿运车和4辆1-2型轿运车数量。6.2.2 最优运输路径模型 在得到最少轿运车数量的前提下，需要对整个运输路线优化。方案一和方案二在得到这个结果之后做人工调整，但是这样的分配更多的依赖人的经验，所以不一定能够得到

48、更好的结果。对后续的调整可建立一个优化模型，计算出调整后的各类型轿运车数量。由前面可知，最少需要25辆轿运车运输所有的乘用车需求。对每一辆轿运车编号，即有辆轿运车。此时的目标函数变为所有轿运车行驶的最短路程其中表示第辆轿运车最短行驶距离。由题目可知，每一辆轿运车在4个目的地时有可能卸下一部分的I型和II型轿运车，而所有卸载的I型和II型乘用车数量与这辆轿运车能够装载的I型和II型乘用车的数量相等，所以有约束条件表示第辆轿运车在目的地放下I型乘用车的数量；表示第辆轿运车在目的地放下II型乘用车的数量；表示第辆轿运车装载I型乘用车的数量；表示第辆轿运车装载II型乘用车的数量。所有轿运车在目的地卸下

49、的I型和II型乘用车的数量与该目的地需要的I型和II型乘用车的数量相同，于是有约束条件表示目的地需要I型乘用车的数量；表示目的地需要II型乘用车的数量。于是可以得到最优运输模型为 （7）6.3 模型的求解6.3.1遗传算法的介绍 遗传算法提供了一个求解问题的通用框架，可用于各种优化问题1。遗传算法是一种基于自然选择和群体遗传机理的搜索算法，它模拟了自然选择和遗传过程中的繁殖、交叉和突变现象。在利用遗传算法求解问题时，问题的每个可能的解都被编码成一个“染色体”，即个体，若干个个体构成了群体（所有可能解）。在遗传算法开始时，总是随机地产生一些个体（即初始解）。根据预定的目标函数对每个个体进行评估，

50、给出了一个适应度值。基于此适应度值，选择个体用来复制下一代。选择操作出现了“适者生存”的原理，“好”的个体被选择用来复制，而“坏”的个体则被淘汰。然后选择出来的个体经过交叉和变异算子进行再组合生成新的一代。这一群新个体由于继承了上一代的一些优良性状，因而在性能上要优于上一代，这样逐步朝着更优解的方向进化2。 因此，遗传算法可以看成是一个由可行解组成的群体逐步进化的过程。基于本题目所要求解的模型性能而言，这种分配形式需要在众多的随机数据组合中找到最优的解，所以可选用遗传算法作为该模型的基础算法。6.3.2利用遗传算法求解过程（1）编码与解码用遗传算法求最优解时，染色体的编码方法和解码方法非常重要，决定了算法实现的难易程度。本文选取为染色体进行编码，其中表示第辆轿运车在目的地下载的I型乘用车数量，表示第辆轿运车在站点下载的II型乘用车数量。由染色体可解码得到每辆轿运车行驶距离。例如1号轿运车在A、B、C、D放下的I型和II型乘用车分别为0 0 0 3 0 0 2 3,由于由4个目的地，则可以将每辆轿运