1、CD总数1-1型1695211-2型4总量25针对问题五，作为问题四的扩展研究，类似于问题四建立了双目标规划模型。由于乘用车的种类达到了45种，导致轿运车的装载组合方案急剧增多。如果仍采用穷举法确定装载组合方案，将产生“组合爆炸”。为此，采用基于排样算法的装载优化算法，来避免这种现象。这种算法的基本流程是：首先按照乘用车的宽、高将乘用车分为“高”、“低窄”、“低宽”三种车型； 然后根据不同类型的乘用车在不同目的地的需求量，构建关系树；接着根据关系树和启发式调整优化算法来确立初步配载方案；最后验证配载方案是否满足约束条件以求得最终方案。其中，启发式调整优化算法仍然是基于经验的，这里主要考虑轿运车
2、上层空间的利用率最大化和距离较远的点以尽可能地减少轿运车的数量，同时也要满足不同轿运车型之间的数量比例约束。最终求得的各目的地轿运车的详细使用量如下表所示，并且完成运输任务所需行驶的总里程为35140。序号目的地A目的地B目的地C目的地D目的地E余量14721031112815目的地总量34291927轿运车总量118关键词：整车物流 整数规划 分支定界法 经验阈值 启发式调整优化 排样算法一、 问题重述1.1 问题背景整车物流指的是按照客户订单对整车快速配送的全过程。随着我国汽车工业的高速发展，整车物流量，特别是乘用车的整车物流量迅速增长。乘用车生产厂家根据全国客户的购车订单，向物流公司下达
3、运输乘用车到全国各地的任务，物流公司则根据下达的任务制定运输计划并配送这批乘用车。为此，物流公司首先要从他们当时可以调用的“轿运车”中选择出若干辆轿运车，进而给出其中每一辆轿运车上乘用车的装载方案和目的地，以保证运输任务的完成。“轿运车”是通过公路来运输乘用车整车的专用运输车，根据型号的不同有单层和双层两种类型，而单层轿运车实际中很少使用，本题仅考虑双层轿运车。在确保完成运输任务的前提下，物流公司追求降低运输成本。但由于轿运车、乘用车有多种规格等原因，当前很多物流公司在制定运输计划时主要依赖调度人员的经验，在面对复杂的运输任务时，往往效率低下，而且运输成本不尽理想。1.2 已知信息（1）每种轿
4、运车上、下层装载区域均可等价看成长方形，各列乘用车均纵向摆放，相邻乘用车之间纵向及横向的安全车距均至少为0.1米，下层力争装满，上层两列力求对称，以保证轿运车行驶平稳。（2）1-1型及2-2型轿运车上、下层装载区域相同；第五问中1-2型轿运车上、下层装载区域长度相同，但上层比下层宽0.8米。（3）受层高限制，高度超过1.7米的乘用车只能装在1-1、1-2型下层，2-2型上、下层均不能装载高度超过1.7米的乘用车。（4）在轿运车使用数量相同情况下，1-1型轿运车的使用成本较低，2-2型较高，1-2型略低于前两者的平均值，但物流公司1-2型轿运车拥有量小，为方便后续任务安排，每次1-2型轿运车使用
5、量不超过1-1型轿运车使用量的20%。（5）在轿运车使用数量及型号均相同情况下，行驶里程短的成本低。1.3 需要解决的问题请为物流公司安排以下五次运输，制定详细计划，含所需要各种类型轿运车的数量、每辆轿运车的乘用车装载方案、行车路线。（前三问目的地只有一个，可提供一个通用程序；后两问也要给出启发式算法的程序，优化模型则更佳）：（1）物流公司要运输车型的乘用车100辆及车型的乘用车68辆。（2）物流公司要运输车型的乘用车72辆及车型的乘用车52辆。（3）物流公司要运输车型的乘用车156辆、车型的乘用车102辆及车型的乘用车39辆。（4）物流公司要运输166辆车型的乘用车（其中目的地是A、B、C、
6、D的分别为42、50、33、41辆）和78辆车型的乘用车（其中目的地是A、C的分别为31、47辆）。（5）根据附件表1给出的物流公司需要运输的乘用车类型（含序号）、尺寸大小、数量和目的地和附件表2给出的可以调用的轿运车类型（含序号）、数量和装载区域大小，采用启发式算法，求解装载、运输方案，并自行设计运输方案的表达形式。二、 模型假设（1） 每辆轿运车装载乘用车的组合是独立的；（2） 轿运车装载乘用车时上下层部分是对称的，即数量一致；（3） 轿运车到达目的地后原地待命，无须放空返回；（4） 轿运车在运输过程中不存在往返情况；（5） 每次卸车成本可以忽略不计。三、 基本符号说明符号符号说明v_n第
7、v辆车的装载组合数L轿运车的长度Cvjk第v辆车第j个装载组合装载第k种类型物品的容量lj第j种乘用车的长度xivj物品i装载在车辆v的第j个装载组合c安全距离yvj车辆v选择第j个装载组合xi第i种方案的使用数量Cij第i种装载组合方案能承载第j种乘用车的数目r长度余量Nj需要装载的第j种乘用车的数量T经验阈值PkO到A、B、C、D、E的距离S轿运车的总路程bjk第j种乘用车运往第k个目的地的数量yik第i种方案去第k个目的地四、 问题分析本文研究的是乘用车物流运输计划问题，通过对轿运车的空间利用率和运输成本进行优化，设计启发式算法，以求解各种运输条件下详细的装载与运输方案，能够使得轿运车的
8、利用率达到最高、运输成本达到最低、行车路线最优。针对题中的五个问题，分析如下：4.1 问题一分析题目要求给出运输车型的乘用车100辆及车型的乘用车68辆时物流公司的运输方案。本问题即将给定数量的车型和车型乘用车装载到1-1型轿运车和1-2型轿运车上，并使得所用的1-1型轿运车和1-2型轿运车数量之和最少，亦即成本最少。并在满足数量最少的情况下，求解车型和车型乘用车的最佳装载组合方案，以使得两种轿运车空间利用率达到最大。由于两种乘用车的高度均不超过1.7米，且其宽度小于轿运车的下层宽度、两倍宽度也不超过轿运车的上层宽度，即车型和车型乘用车可以装载在1-1型和1-2型轿运车的任意层上。所以，问题可
9、以归结为一维组合装车问题，求解的目标是充分利用轿运车的长度，以使得轿运车的长度余量最少，则轿运车的空间利用率也将达到最大。4.2 问题二分析题目要求给出运输车型的乘用车72辆及车型的乘用车52辆时物流公司的运输方案。本问题即将给定数量的车型和车型乘用车装载到1-1型轿运车和1-2型轿运车上，并使得所用的1-1型轿运车和1-2型轿运车数量之和最少，亦即成本最少。并在满足数量最少的情况下，求解车型和车型乘用车的最佳装载组合方案，以使得两种轿运车空间利用率达到最大。由于车型乘用车的高度大于1.7米，根据题目中的要求，只能将其装载在1-1型和1-2型轿运车的下层上。而车型的乘用车，仍然可以装载在1-1
10、型和1-2型轿运车的任意层。问题仍为求解一维组合装车问题，求解的目标是充分利用轿运车的长度，以使得轿运车的长度余量最少。4.3 问题三分析题目要求给出运输车型的乘用车156辆、车型的乘用车102辆及车型的乘用车39辆时物流公司的运输方案。本问题即将给定数量的车型、车型和车型乘用车装载到1-1型轿运车和1-2型轿运车上，并使得所用的1-1型轿运车和1-2型轿运车数量之和最少，亦即成本最少。并在满足数量最少的情况下，求解车型、车型和车型乘用车的最佳装载组合方案，以使得两种轿运车空间利用率达到最大。此问题可以看作是前两问的延伸，此时1-1型轿运车和1-2型轿运车下层均可以装载三种乘用车，而上层只能装
11、载车型和车型轿运车。4.4 问题四分析题目要求给出运输166辆车型的乘用车（其中目的地是A、B、C、D的分别为42、50、33、41辆）和78辆车型的乘用车（其中目的地是A、C的分别为31、47辆）时物流公司的运输方案。本问题可以看作是问题一的延伸，在问题一的基础上将路径加入到了考虑之列，目的地不再相同。问题变成将给定数量的车型和车型乘用车装载到1-1型轿运车和1-2型轿运车上，并运往相应的目的地，以满足各目的地的需求，使得运输成本最少。而影响运输成本的首要因素是轿运车使用数量，其次是行驶里程长短。因而问题转换为求解车型和车型乘用车的最佳装载组合方案，以使得两种轿运车的使用总数量最小且所需的路
12、程最短。这是一个双目标规划问题，此时轿运车有可能不再满足满载的条件。4.5 问题五分析题目要求利用10种不同规格轿运车，来装载45种不同规格的乘用车，以满足A、B、C、D、E五个目的地对45种乘用车的数量需求。本问题可以看作是问题四的扩展研究，只是问题比第四问要复杂的多，但整体的模型是一致的。对于这种NP难问题，寻找最优解是不切实际的，需要重新设计启发式算法，简化目标函数，使其更容易求解，以期能够求得满足约束条件的可行解。五、 问题求解与算法设计5.1装载问题的基本模型5.1.1 模型定性分析在不考虑整车目的地和轿运车的路径选择的情况下，问题可抽象为带装载组合约束的一维装车问题1，即有n个属于
13、l种类型的相同（单位）尺寸的物品，有w辆车，每辆车对这l种类型的物品有几种装载组合，不同车辆的装载组合不同，每辆车选择一种装载组合并严格按照物品组合进行装载。优化目标是在满载的情况下装载最多的物品，同时给出每个物品的具体配载方案。5.1.2 复杂性分析考虑带装载组合约束的一维装车问题的简化问题，当每辆车只有一个装载组合时，问题变为：有l种类型的物品，类型k的物品数Nk，有n个装载组合，第j个装载组合对类型k物品的容量Cjk，对所有类型物品的容量Cj，选择装载组合以尽可能装载最多的物品。已知多维背包问题为NP难问题2，而多维背包问题可以转化为一维组合装车问题的简化问题，则一维组合装车问题的简化问
14、题为NP难问题，显然一维组合装车问题更为复杂，也即一维组合装车问题为NP难问题。5.1.3 一维组合装车问题线性混合整数规划模型3问题最终结果是给出具体的装载方案，即物品装载在哪辆车的哪个装载组合上，因此以物品作为决策主体，物品选择车辆、装载组合。设物品数为m,类型数为l，车辆数为w，第v辆车的装载组合数为v_n，第v辆车第j个装载组合装载第k种类型物品的容量为Cvjk, xivj为物品i是否装载在车辆v的第j个装载组合上的0、1变量，yvj为车辆v是否选择第j个装载组合的0、1变量，则有如下数学模型： （5-1）优化目标为物品装载数最多；约束式第一式表示一辆车最多只能选择一种装载组合；第二式
15、表示一个物品最多只能被装载到一辆车的某个装载组合上；第三式表示每辆车必须严格按照装载组合装满每种类型的物品；第四、五式定义了变量的取值范围。5.2 两阶段装载优化模型的建立5.2.1 实际问题的分析与简化在本问题中，有三种类型的乘用车，其数量根据具体的运输任务而定，每种车的规格均不同。轿运车也有两种，其规格也有较大差异。现要考虑将给定数量的三种类型的乘用车装载到两种类型的较运车上，但轿运车的数量可以无限多。为了在保证完成运输任务的前提下，降低整车物流的运输成本，目标函数变为在满足满载的情况下，选择最优装载组合方案，使得所使用的轿运车数量最少。而满载的条件在本问题中不再适用，我们简化为考虑轿运车
16、的空间利用率最大，为此，建立了两阶段装载优化模型4。5.2.2 装载组合方案的确定在给定运输任务的乘用车类型后，根据各乘用车的规格和各装载用轿运车的规格，首先确定1-1型和1-2型轿运车每层可以装载的乘用车类型，然后依据1-1型和1-2型轿运车的实际长度，再加上纵向的安全车距的限制，采用穷举法，可以确立各类型轿运车的所有装载组合。假定轿运车的长度为L，第j种乘用车的长度为lj（j = 1, 2, 3分别代表型、型、型），并用kj表示装载组合中承载的第j种乘用车的数目，安全距离c=0.1，满足要求的装载组合方案应满足（只考虑单个下层的情况，其它层类似）： （5-2）5.2.3 两阶段装载优化模型
17、（1）第一阶段：空间利用率最大化优化模型 a）目标函数的确定考虑到无论是使用1-1型轿运车还是1-2型轿运车，均采用双层装载。而且为了安全，下层装载的是重心高度较高的乘用车，如车型乘用车。再者，车型和车型乘用车的宽度均在轿运车的允许范围之内。因此，轿运车在装载乘用车时，在高度和宽度上并不存在利用的概念，在最大化空间利用率时仅需考虑长度的充分利用即可，而具体装载辆数取决于乘用车的类型。设Ci，j表示第i种装载组合方案能承载第j种乘用车的数目（i = 1, 2， , m, m+1, , M，m为使用1-1型轿运车的最大方案数，M为分别使用1-1型、1-2型轿运车的总方案数之和；j = 1, 2,
18、3, 4, 5, 分别表示上（型车放在上层，后面依次类推）、上、下、下、下五种情况），n表示轿运车的列数（1-1型为2, 1-2型为3, 2-2型为4），则目标函数可以表示为：（5-3） b）约束条件的确定轿运车装载时，应保证乘用车与乘用车之间，乘用车与轿运车端壁之间的最小间隙, 避免发生碰撞，此安全距离为0.1米，同时应满足轿运车的装载长度约束。即，满足的约束条件如下： （5-4）（2）第二阶段：运输成本最小化优化模型由于影响整车物流运输成本高低的主要因素首先是轿运车使用数量，其次是在轿运车使用数量相同情况下的轿运车使用成本，最后是行驶里程成本。而在前三问的模型中，不考虑路径问题，因而我们以
19、轿运车的使用数量最少为主要考虑因素，对组合方案进行优化，以使运输成本最小。设第i种方案的使用数量为xi（i = 1, 2， , m, m+1, , M），则目标函数为： （5-5）由于1-1型轿运车的使用成本较低，2-2型较高，1-2型略低于前两者的平均值。为了降低成本，应使1-2型轿运车使用量少于1-1型轿运车，且每次1-2型轿运车使用量不超过1-1型轿运车使用量的20%，这也符合物流公司1-2型轿运车拥有量小的实际；再者，无论采用哪些组合方案，都必须满足物流公司的运输安排，努力完成任务。 （5-6）其中，Nj为需要装载的第j种乘用车的数量。5.2.4基于经验阈值的求解优化方法考虑到在求解上
20、述两阶段装载优化模型时，问题归结为一个双目标规划问题，实际求解时较为困难。为此，对问题进行重新分析，空间利用率最大可以等价为长度余量最少，而组合方案的求解时也可以通过考虑长度余量来进行分析。设长度余量为r，则 （5-7）根据实际情况，r应满足非负的要求。由于每种方案的长度余量不同，但对于每种类型的轿运车的所有装载组合方案，其长度余量必有一个取值范围，我们可以考虑人为的给定一个阈值。这样可以对组合方案进行有目的的筛选，也可以解决因穷举法产生的“组合爆炸”问题，同时也考虑了空间利用率最大。因而，求解两阶段装载优化问题最终归结为一个整数规划问题 （5-8）其中，T为阈值，根据经验获得，在本文的计算中
21、，T取2。5.3 装载优化模型的通用求解算法设计5.3.1 求解整数规划的分支定界算法分支定界算法是一种隐枚举法,是整数规划中常用的算法之一5。它的主要思想是根据某种策略将原问题松弛问题的可行域分解为越来越小的子域, 并检查每个子域内整数解的情况, 直到找到最优整数解或证明整数解不存在。分支定界法从求松弛问题开始, 将问题可行域分为许多的子域（最通常的分解方式是“两分法”）,这一过程称为分支；通过分支找到更好的整数解来不断的修改问题的上下解,这一过程称为定界。定界的目的是为了测定界的趋势,留下有价值的或尚不能判定的分支。删除肯定不存在最优解的分支, 称之为剪枝, 以达到加速收敛, 简化运算的目
22、的。不同的分支定界方法在于分支、定界和剪枝的不同处理手段上, 其算法的一般步骤可概括为：Step1：初始化。选择可行域的S的初始松弛集合F，满足；初始可行点集合，上界，令P=F，计算下界，并令。在计算的过程中，若有必要，则更新Q和Step2：分割。将F分割成有限个子集Fi，（指标集）满足，令Step3：剪枝。对每个，计算f 在子集Fi 上的下界，使其满足，利用在计算）的过程中所发现的所有可行点修正集合Q，同时按照合适的删除规则，删除P中所有不包含最优解的Fi或Fi的一部分，剩余集合不妨仍记为P；Step4：定界。令，Step5：终止判断。若（充分小的正数），则终止算法。否则，从P中挑选合适的子
23、集F，转入步骤2。5.3.2 启发式调整优化启发式算法3是一种基于直观或经验构造的算法,在可接受的花费（指计算时间和空间）下给出待解决组合优化问题每一个实例的一个可行解,该可行解与最优解的偏离程度不一定事先可以预计。利用分支定界法求解整数规划问题（5-8）所得的解有时并不是最优解，此时就需要进行调整，这时只需要在保证轿运车总数量不变的情况下，对可行解进行启发式的局部调整即可。这种启发式的调整思路大致如下：（1） 放宽阈值T，扩大解的范围；（2） 根据经验，将新解范围中的某一种方案的数量与可行解相应的方案数量进行替换；（3） 验证新的解是否满足约束条件，如果新解满足约束条件且新解的轿运车数量总数
24、不超过可行解，则新解即为可能的最优解；（4） 在这些所有可能的最优解中，寻找轿运车数目最少的即为最优解。启发式算法简单直观，速度快，容易被接受，但在最坏情况下，也不能获得最优解，这时就只能通过人工干预进行调整，以获得最优解。5.3.3 通用算法设计图1 通用算法流程图本文通过前三问的求解，归纳总结出了一种适合求解前三问的通用算法，并用一个通用程序进行了实现。所实现的通用程序，能够满足前三问运输任务，并能按照题目要求输入输出最优解。算法的流程图如图1所示，这里，简单叙述一下通用算法的主要步骤：分别输入轿运车与乘用车的规格数据（长、宽、高），并输入需要运输的三种乘用车的数量，如果没有某种乘用车，则
25、输入0；通过（5-2）式来计算所有可能的轿运车装载方案，并进行编号；利用分支定界法求解式（5-8）所示的整数规划问题，并对所求得的解进行验证，如果求得的解就是最优解，则转到Step6；否则继续；按照上节所述的启发式调整优化方法继续求解优化，寻找最优解，并对所求得的解进行验证，如果所得的解即是最优解，则转到Step6；对上步所得的可行解进行人工干预，局部小范围调整方案，以获得最优解；Step6：按照题目要求输出装载方案与所需轿运车数量的Excel格式。5.4 问题一求解本问题中，N1=100，N2=68，N3=0，带入式（5-8）中，可得问题一的具体模型为： （5-9）将N1=100，N2=68，N3=0输入到通用程序中，可以求得11种装载组合方案，如表1所示，其中前5种为使用1-1型轿运车时的所有可能装载组合方案，后6种为使用1-2型轿运车时的所有可能装载组合方案。表1 问题一的所有可能装载组合方案方案上层装载型乘用车数目上层装载型乘用车数目下层装载型乘用车数目下层装载型乘用车数目最终求得的所有装载方案情况如表2所示：表2 问题一的装载方案轿运车类型相同类型、相同装载方式的车辆数装在上层序号为1乘用车数量装在上层序号为2乘用车数量装在上层序号为3乘用车数量装在下层序号为1乘用车数量装在下层序号为2装在上层序号为3中间停靠地目的地统计的轿运车数量，如表3
