基于整数规划模型的乘用车最优运输方案

2015-12-28周靖靖刘金杰张万里

重庆科技学院学报（自然科学版） 2015年2期

周靖靖刘金杰张万里

(1.重庆师范大学经济与管理学院，重庆 401331;2.重庆师范大学数学学院，重庆 401331)

1 问题叙述

物流问题是近年来的研究热点之一。张腾松研究了整车物流配送路径的优化设计［1］。陈赛虎利用整数规划模型研究了轿车物流配载的优化问题［2］。秦绪伟等人研究了整车物流网络的集成优化问题［3］。本次研究主要解决2014年全国研究生数学建模竞赛提出的乘用车最优运输问题。具体问题背景如下:

双层轿运车又分为3种子型:上下层各装载1列乘用车，故记为1-1型;上层装载2列，下层装载1列，记为1-2型;上、下层各装载2列，记为2-2型，每辆轿运车可以装载乘用车6～27辆。

装载具体要求:每种轿运车上、下层装载区域均可视为长方形，各列乘用车均纵向摆放，相邻乘用车之间纵、横向安全车距均至少保持0.1 m，下层力争装满，上层两列力求对称，以保证轿运车行驶平稳。受层高限制，高度超过1.7 m的乘用车只能装在1-1型和1-2型的下层。乘用车、轿运车规格见表1和表2。

各因素关系:影响成本的要素首先是轿运车使用数量;其次，在轿运车使用数量相同的情况下，1-1型轿运车的使用成本较低，2-2型较高，1-2型略低于前两者的平均值，但物流公司1-2型轿运车拥有量小，为方便后续任务安排，每次1-2型轿运车使用量不超过1-1型轿运车使用量的20%;再次，在轿运车使用数量及型号均相同的情况下，行驶里程短的成本较低。

表2 轿运车规格 m

因为该物流公司是全国性公司，在各地均会有整车物流业务，所以轿运车到达目的地后原地待命，无须放空返回。每次卸车成本几乎可以忽略。

公司安排2次运输，在此需要制定详细计划，含所需各种类型轿运车的数量、每辆轿运车的乘用车装载方案。需要建立模型解决以下问题:

(1)最低成本下，物流公司运输Ⅰ车型的乘用车100辆及Ⅱ车型的乘用车68辆。

(2)最低成本下，物流公司运输Ⅱ车型的乘用车72辆及Ⅲ车型的乘用车52辆。

2 模型假设

(1)仅考虑双层轿运车型号;

(2)不考虑卸车成本;

(3)轿运车在运行过程中不会发生故障;

(4)轿运车到达目的地后原地待命，无须放空返回;

(5)各列乘用车均纵向摆放;

(6)假设各类轿运车的装载区域和乘用车均是长方形。

模型中各符号说明见表1。

表1 模型中各符号说明

3 模型建立及求解

为确定乘用车的最优运输方案，结合经典贪婪算法思想，在此给出改进的贪婪算法。算法主要步骤如下:

Step 1:输入乘用车的数量和类型，转Step 2;

Step 2:计算能够装载全部乘用车所需的轿运车型号及其最少数量，转Step 3;

Step 3:按每类轿运车装载后剩余空间最小为目标安排计算所需乘用车类型和数量转Step 4;

Step 4:计算具有相同装载方案的乘运车数量;并计算出每辆轿运车上层的装载方案;最后计算每类乘用车剩余数量，转Step 3;

Step 5:输出每辆轿运车的装载方案，结束。

3.1 问题(1)的模型建立及求解

3.1.1 确定最少轿运车车辆使用数

假设需要1-1型轿运车n1辆，1-2型轿运车n2辆，需要进行装载的Ⅰ车型乘用车有c1辆，Ⅱ车型乘用车有c2辆，则轿运车的使用数量越少越符合物流公司节约成本的要求［7］，因此目标函数为min(n1+n2)。又由每次1-2型轿运车使用量不超过1-1型轿运车使用量的20%，故有n2≤20%n1。首先考虑1-1型轿运车与1-2型轿运车的下层宽度，w1和w2≤W1，w1和w2≤W2;再考虑1-2型轿运车的上层宽度: