货运公司的运输问题摘要为了节约成本，提高货运公司的运输效率，本文对集送货可拆分的车辆路径问题进行了研究该问题允许一个任务点被访问多次，也允许同一车辆访问同一任务点多于一次针对此问题的特点，利用优化思想建立了线性规划模型、0-1 规划模型和最优化模型，解决了运输的最小运费问题、每辆运输车的运输方案问题，从而使运输满足各公司当天的需求量问题一：由问题一中的货运问题可运用线性规划模型，在卸货顺序约束下，对每次出车求局部最小费用且尽可能满载，最后得出全局解分析问题可知，费用最少问题与出车次数、调度安排、运输成本均有关系，由公司与原材料的关系、港口与公司间路程的关系及原材料的重量分别建立3个矩阵，以公司需求与工作时间限制为约束条件，最小的运输费用为目标函数，建立一个线性规划模型考虑到调度问题时，分两种情况——顺时针与逆时针此时，由于顺时针与逆时针是处于非此即彼的对立关系，想到建立一个 0-1 规划模型，并通过Lingo11.0版本的软件进行求解，得到了运输车次为28，出动运输车6辆，所以总费用为 4817 元问题二：此问题的条件由问题一的运输过程中不允许掉头改为运输过程中可以掉头，因此该问题的模型与算法与问题一如出一辙。
此问题的特殊之处即为途中可以掉头，因此在运输车空载时，可以对行走方向进行选择，掉头回到港口或者继续原方向行驶由于题中路程唯一，车速不变，可以得出如下定理：一、车辆载重行程是各公司到港口最短路，且载重费用固定不变；二、车辆当且仅当运完最后一件货才调头；推论：运载里程与空载里程相同，且每次出车均不绕圈工作我们以每次运输量为决策变量，最小总费用为目标，建立整数线性规划模型，使用LINGO软件编程求解最小运费及运次方案，可以求得总费用4680.2元，总运次28次问题三：当各个公司间都有或者部分有道路直接相通时，此问题仍然可以使用前面建立的模型,只是运输路程中的最短路径已经发生了变化,故而此问题可以使用同一个改进后的模型实现.关键字：车辆路径问题 线性规划模型 0-1 规划模型 一、问题重述货运公司需要为多个任务点提供服务，各个任务点位置已知，具有送货需求，且需求量可以超过车辆容量，车辆从货运公司出发，载运一定的货物到达任务点，采用先卸小件、后卸大件的方式完成任务，且不得将已卸的货物装车，车内货物可以根据装卸货物的实际情况进行很好的位置调整，或者能够满足装卸货物的要求，任务点的送货需求量可以拆分，由不同车辆或同一车辆多次完成，所有车辆保证途中不得超载，合理安排车辆的行驶路线，在行驶途中可调头和不可调头两种情况下，使得运费之和最小。
分析当各个公司间都有或者部分有道路直接相通时，运输调度的的难度及解决的办法所需要的具体数据图如下图1、图2：图1 唯一的运输路线图和里程数图2 各个公司对每种材料的需求量（单位/天）公司编号各种材料的需求量（单位/天）ABC①415②152③204④312⑤124⑥043⑦225⑧531二、问题分析由题意可知，目的就是为了建立一种模型，解决运输的最小运费问题，每辆运输车的运输方案问题，从而使运输满足各公司当天的需求量2.1问题1的分析问题一中，将货运问题转化为线性规划模型，题中给出6辆可用的运输车，考虑到每辆车只能装载6吨重的货物，并优先考虑发挥每辆运输车最大的装载能力，可得出每辆车的装载方案有以下四种：6个C、2个B、1个A 2个C、1个B 3个C由此，根据8个公司对三种原材料的每日需求量，即可建立一个线性规划模型此外，还要考虑运输车的调度问题，由于出车方向不定，分为逆时针和顺时针两种情况，而且这两种情况是非此即彼的对立关系，这属于 0-1 规划问题我们令p表示采用顺时针运输的情况，令q表示采用逆时针运输的情况再结合题目中给出的其他相关数据，即可求得最优解2.2问题2的分析问题二中的解决方法和第一问中的解决方法是类似的，不过由于这时候运输车可以掉头，故可以减少由于运输车在途中空载的路程。
根据题中路程唯一、车速不变的条件，及卸货顺序约束，车容量约束，公司需求约束，我们以每次运输量为决策变量，最小总费用为目标，建立混合整数线性规划模型，使用LINGO软件编程求解最小运费及运次方案2.3问题3的分析问题三中，当各个公司间都有或者部分有道路直接相通时，此问题仍然可以使用前面建立的模型,只是运输路程中的最短路径已经发生了变化,故而此问题可以使用同一个改进后的模型实现.三、模型假设1. 假设货运公司都是先考虑如何安排运输方式以减少经费支出，再考虑节省人力和出车次数最少的情况；2. 假设运输车行驶过程中不考虑塞车抛锚现象，运输过程中所有路况相同，以保证每辆车每天可以达到最大的作业时间；四、符号说明 =(e，f，g)：一单位A、B、C原材料的净重量； ：第j个公司对第i种原材料的总的需求量；m ：运输车采用顺时针运输的次数； n ：运输车采用逆时针运输的次数；k ：总车次； : x次中某一次顺时针运货方案； ：y次中某一次逆时针运货方案； p=1：表示车采用顺时针运输；p=0：表示车不采用顺时针运输； q=1：表示采用逆时针运输；q=0：表示第 i 辆车不采用逆时针运输； t ：运输车在第t公司处全部卸完货物； a ：载重运费 b ：空载运费 c ：运输车容量； s ：总路程；（另外有些变量为局部变量，将在该符号具体的位置予以说明）五、模型的建立与求解5.1问题一首先，建立求解出满足每个公司的需求的线性规划模型，在卸货顺序,车次总数,每次载货量等的约束下，对每次出车求局部最小费用且尽可能满载，最后得出全局解。
5.1.1模型准备——时间窗转换为车次约束分析因为每辆运输车有八小时的工作时间限制,此处因为只考虑总费用最小,所以计划把时间窗的约束转换成车次使用次数.以下将通过对货物总量的当考虑运输车尽量发挥其运载最大能力时，有如下四种方式： （a）1A+2C、（b）2B、（c）6C、（d）B+3C我们分别设这四种方式需要调度的次数为 Q1、Q2、Q3、Q4，这样我们就可以建立如下数学模型: min S=Q1+Q2+Q3+Q4 s.t. Q1〉=18 2Q2+Q4〉=18 2Q1+6Q3+3Q4〉=26 Q1、Q2、Q3、Q4>=0用LINGO 进行求解可以得到 S=27，Q1=18，Q2=9，Q3=0，Q4=0即可得理想的总出车次数为27次下面运算出车次数的最大值从港口出发行驶完整的一圈的路程为60公里，运输车平均速度为60公里／小时，则行驶完整一圈的时间为1小时考虑到运输车的装卸过程，假设装卸各一次，装货时间用15分钟、卸车时间平均为10分钟，则装卸各一次后行驶完整一圈的时间共需1小时25分钟考虑全天工作不得超过8小时，则照此一辆运输车最多一天行驶5次由于考虑总费用最少，所以不可能让运输车空载行驶完整的一圈，每辆运输车行驶途中至少要卸一次货。
综上，一辆运输车在一天内，最多行驶5次港口处共有6辆运输车，因此，一天内，港口发车次数最大为30综上可得：（m+n为发车总次数）,从而解除了时间窗的约束.5.1.2模型建立根据8个公司和三种原材料的关系，构造一个3行8列的矩阵——，以行表示3种原材料、列表示8个公司考虑到运输车采用顺时针或逆时针的问题，将矩阵分成以下两种：（1）运输车采用顺时针时，3×8矩阵表示为：（其中i表示第i种原材料、j表示第j个公司、m表示运输车采用顺时针运输的次数），列从左到右按照①—⑧公司的顺序依次排列；（如图1）（2）运输车采用逆时针时，3×8矩阵表示为：（其中i表示第i种原材料、j表示第j个公司、n表示运输车采用逆时针运输的次数），列从左到右按照①—⑧公司的顺序依次排列（如图1）该3×8矩阵中其中的一个数字表示顺时针运输的第x次在第j个公司卸载了第i种原材料例如下图中表示某一运输车在①公司处卸下1单位C材料，在②公司处卸下2单位C材料、1单位B材料，之后运输全部卸完货物，之后空载行驶回港口 ① ② ③ ④ ⑤ ⑥ ⑦ ⑧ ABC 例： 图1 、矩阵根据港口到8个公司的路程，构造一个8行1列的矩阵——，以行表示8个公司、列表示从港口分别到各个公司的路程值。
同理，考虑到运输车采用顺时针或逆时针的问题，将矩阵分成以下两种：（1）运输车采用顺时针时，8×1矩阵表示为：，表示运输车采用顺时针行驶从港口到j公司，行从上到下按照①—⑧公司的顺序依次排列（如图2）；（2）运输车采用逆时针时，8×1矩阵表示为：，表示运输车采用逆时针行驶从港口到j公司，行从上到下按照①—⑧公司的顺序依次排列（如图3）10⑨① ② ③ ④ ⑤ ⑥ ⑦ ⑧ 图2 矩阵⑨① ② ③ ④ ⑤ ⑥ ⑦ ⑧ 图3 矩阵设运费最小为此问题的目标函数F，综上，可得到此问题的目标函数：F=a×+k×10+6×20约束条件为：设5.1.2模型求解Step1通过分析各公司对原材料的需求量，可按照将每辆运输车最大的装载能力，简化需处理的数据。
根据每辆运输车最多装载6吨，可得到每辆运输车的装载方案：(a)1A+2C、 (b)2B、(c)6C、(d)B+3C据此，逐个分析各个公司的需求量，将每个公司的需求进行拆分，其中可以符合上述四种运载方案的最短路径方案则可以肯定为最优解的一部分，因此这部分的数据不需要通过建立的模型再计算，从而使得需处理数据得到极大的简化例如①公司：对A、B、C三种原材料需求量分别为：4、1、5此数据可分为两部分：2、0、4与2、1、1，前一部分按照装载方案1A+2C通过两次运输即可完成，后一部分无法套用上面的四种中的任意一种，因此①公司仍需处理的数据为：2、1、1由以上方法，可总结为下表2表2公司编号调度方案次数方案①21A+2C1A+2C②31A+2C2B2B③21A+2C1A+2C④11A+2C⑤21A+2C2B⑥21B+3C2B⑦31A+2C1A+2C2B⑧12BStep2根据Step1，可以将原始各个公司对每种材料的需求量（如附表1）简化为下表2——各个公司对每种材料简化后的需求量表3 各个公司对每种材料简化后的需求量公司编号各种材料的需求量（单位/天）ABC①211②010③000④2。