参赛密码
                                          （由组委会填写）
全
第十一届华为杯全国研究生数学建模竞赛
学    校
西安理工大学
参赛队号
队员姓名
参赛密码
                                          （由组委会填写）
           
第十一届华为杯全国研究生数学建模竞赛
题 目            乘用车物流运输计划问题
摘      要：
本文主要解决的是乘用车整车物流的运输调度问题，通过对轿运车的空间利用率和运输成本进行优化，建立整数规划模型，设计了启发式算法，求解出了各种运输条件下的详细装载与运输方案。
针对前三问，由于不考虑目的地和轿运车的路径选择，将问题抽象为带装载组合约束的一维
装车问题，优化目标是在保证完成运输任务的前提下尽可能满载，选择最优装载组合方案使得所使用的轿运车数量最少。对于满载的条件，将其简化为考虑轿运车的空间利用率最大，最终建立了空间利用率最大化和运输成本最小化的两阶段装载优化模型。该模型类似于双目标规划模型，很难求解。为此，将空间利用率最大转换为长度余量最少，并为其设定一个经验阈值，将问题转换为求解整数规划问题，利用分支定界法进行求解。由于分支定界法有时并不能求得最优解，设计了一种基于阈值的启发式调整优化算法。最后，设计了求解该类问题的通用算法程序，并对前三问的具体问题进行了求解和验证。通过求解得出，满足前三问运输任务的1-1型轿运车和1-2型轿运车数量如下表所示（具体的乘用车装载方案见表2、表5、表7）：
    第一问        第二问        第三问
1-1      16            12            25
1-2      2            1              5
针对问题四，其是在问题一的基础上加入了整车目的地的条件，需要考虑最优路径的选择。在运输成本上，加入了行驶里程成本，因而可以建立所使用的轿运车数量最少和总里程最少
的双目标整数规划模型。对于此种模型，可以采用前三问所设计的通用算法进行求解。此时，需要重新设计启发式调整优化算法。为此，根据路线距离的远近和轿运车数量需要满足的比例约束条件设计了新的调整优化方案。最终求得的各目的地的轿运车使用数量如下表所示，此时的总路程为6404，具体装载方案见表9。
A
B
C
D
总数
1-1型
1
6
9
5
21
1-2型
4
0
0
0
4
总量
5
6
9
5
25
针对问题五，作为问题四的扩展研究，类似于问题四建立了双目标规划模型。由于乘用车的种类达到了45种，导致轿运车的装载组合方案急剧增多。如果仍采用穷举法确定装载组合方案，将产生“组合爆炸”。为此，采用基于排样算法的装载优化算法，来避免这种现象。这种算法的基本流程是：首先按照乘用车的宽、高将乘用车分为“高”、“低窄”、“低宽”三种车型； 然后根据不同类型的乘用车在不同目的地的需求量，构建关系树；接着根据关系树和启发式调整优化算法来确立初步配载方案；最后验证配载方案是否满足约束条件以求得最终方案。
其中，启发式调整优化算法仍然是基于经验的，这里主要考虑轿运车上层空间的利用率最大化和距离较远的点以尽可能地减少轿运车的数量，同时也要满足不同轿运车型之间的数量比例约束。最终求得的各目的地轿运车的详细使用量如下表所示，并且完成运输任务所需行驶的总里程为35140。
序号
目的地A
目的地B
目的地C
目的地D
目的地E
余量
1
0
14
7
0
0
0
物流论文
2
0
7
0
10
0
1
3
11
0
0
0
11
0
4
12
0
3
0
0
0
5
2
0
0
0
8
0
6
0
0
0
0
0
25
7
0
0
4
0
0
0
8
0
1
15
0
0
0
9
5
0
0
0
0
0
10
4
3
0
1
0
1
目的地总量
34
25
29
11
19
27
轿运车总量
118
关键词：整车物流 整数规划 分支定界法 经验阈值 启发式调整优化 排样算法
一、
问题重述
1.1 问题背景
整车物流指的是按照客户订单对整车快速配送的全过程。随着我国汽车工
业的高速发展，整车物流量，特别是乘用车的整车物流量迅速增长。
乘用车生产厂家根据全国客户的购车订单，向物流公司下达运输乘用车到全国各地的任务，物流公司则根据下达的任务制定运输计划并配送这批乘用车。为此，物流公司首先要从他们当时可以调用的“轿运车”中选择出若干辆轿运车，进而给出其中每一辆轿运车上乘用车的装载方案和目的地，以保证运输任务的完成。“轿运车”是通过公路来运输乘用车整车的专用运输车，根据型号的不同有单层和双层两种类型，而单层轿运车实际中很少使用，本题仅考虑双层轿运车。
在确保完成运输任务的前提下，物流公司追求降低运输成本。但由于轿运车、乘用车有多种规格等原因，当前很多物流公司在制定运输计划时主要依赖调度人员的经验，在面对复杂的运输任务时，往往效率低下，而且运输成本不尽理想。
1.2 已知信息
（1）每种轿运车上、下层装载区域均可等价看成长方形，各列乘用车均纵向摆放，相邻乘用车之间纵向及横向的安全车距均至少为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型轿
运车使用量不超过1-1型轿运车使用量的20%。
（5）在轿运车使用数量及型号均相同情况下，行驶里程短的成本低。
1.3 需要解决的问题
请为物流公司安排以下五次运输，制定详细计划，含所需要各种类型轿运车的数量、每辆轿运车的乘用车装载方案、行车路线。（前三问目的地只有一个，可提供一个通用程序；后两问也要给出启发式算法的程序，优化模型则更佳）：
（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辆）。
（5）根据附件表1给出的物流公司需要运输的乘用车类型（含序号)、尺寸大小、数量和目的地和附件表2给出的可以调用的轿运车类型（含序号)、数量和装载区域大小，采用启发式算法，求解装载、运输方案，并自行设计运输方案的表达形式。