一、问题重述

某地区有8个公司(如图一编号①至⑧)，某天某货运公司要派车将各公司所需的三种原材料A,B,C从某港口(编号⑨)分别运往各个公司。路线是唯一的双向道路(如图１)。货运公司现有一种载重 6吨的运输车，派车有固定成本20元/辆，从港口出车有固定成本为10元/车次(车辆每出动一次为一车次)。每辆车平均需要用15分钟的时间装车，到每个公司卸车时间平均为10分钟，运输车平均速度为60公里／小时(不考虑塞车现象)，每日工作不超过8小时。运输车载重运费1.8元/吨公里，运输车空载费用0.4元/公里。一个单位的原材料A,B,C分别毛重4吨、3吨、1吨，原材料不能拆分，为了安全，大小件同车时必须小件在上，大件在下。卸货时必须先卸小件，而且不允许卸下来的材料再装上车，另外必须要满足各公司当天的需求量(见表１)。 问题：

1、货运公司派出运输车6辆，每辆车从港口出发(不定方向)后运输途中不允许掉头，应如何调度(每辆车的运载方案，运输成本)使得运费最小。

2、每辆车在运输途中可随时掉头，若要使得成本最小，货运公司怎么安排车辆数？应如何调度？

3、(1)如果有载重量为4吨、6吨、8吨三种运输车，载重运费都是1.8元/吨公里，空载费用分别为0.2，0.4，0.7元/公里，其他费用一样，又如何安排车辆数和调度方案？(2)当各个公司间都有或者部分有道路直接相通时，分析运输调度的难度所在，给出你的解决问题的想法(可结合实际情况深入分析)。

图１ 唯一的运输路线图和里程数

二、符号说明

x1x2x3x4S

表示为一个车装一单位A和两单位C； 表示为一个车装六单位C； 表示为一个车装两单位B；

表示为一个车装一单位B和三单位C； 表示最小运输次数；

表示为一个车装一单位A和一单位C； 表示为一个车装一单位A； 表示第i次运输装A的单位数 ； 表示第i次运输装B的单位数； 表示第i次运输装C的单位数；

x5x6

Xi1Xi2Xi3

Yi1Yi2Yi3P

表示第i次运输A到达目的地所走的路程； 表示第i次运输B到达目的地所走的路程； 表示第i次运输C到达目的地所走的路程；

表示运输车的方向（等于0按照顺时针即○9 ○1 ○2；等于1按照逆时针即○9

○8 ○7）；

M

表示最小成本；

表示第i次运输j的所走单位路程的单位成本；

Zij

a 表示8个公司对A的总需求量；

b

表示8个公司对B的总需求量；

c 表示8个公司对C的总需求量；

三、模型假设

1．假设每辆车装载时发挥其最大的装载能力；

2．假设货运公司都是先考虑节省人力和出车次数最少的情况下再考虑如何安排运输方式以减少经费支出；

3．假设运输车行驶过程中不考虑塞车等各种抛锚现象，以保证每辆车每天可以达到最大的作业时间