货运公司的运输问题

摘要 货运公司的运输问题直接关系到货运公司的经济效益和长远发展。本文以线性规划为基础，通过建立线性规划模型、图论模型以及通过0-1规划研究了具有供求平衡、有序卸货特点的运输问题，求解最小运费，通过优化来确定运输线路和卸货顺序，从而得出最佳运输方案。 货运公司的运输问题是涉及最短路径、最少运费、合理的卸货顺序的配送优化问题，要综合考虑运输路径、装载方式以及卸货顺序等方面。 本题中已给出了唯一的路线图、各公司所需材料量和相关费用。首先，题目规定派出6辆6吨车，出车成本既定，就要尽量减少出车次数，同时合理规划路线和卸货顺序。为此建立了两个线性规划模型。 模型Ⅰ：线性规划模型 在不考虑运输路线和卸货过程，要减少出车次数，建立简单的线性规划模型求出最少出车次数S为27次。在这个前提下，由于出车后不能掉头，再考虑每个车次的出车方向和运载方式。由于出车不是顺时针就是逆时针，采用0-1规划来确定出车方向，以运输量为决策变量，以车容量、卸货顺序和各公司需求建立线性规划模型求解。 模型Ⅱ:图论模型 由于模型中有大量0-1规划需计算，没有很好的算法，建立图论模型来优化派遣方案。在图论模型中，首先尽量满载，其次利用贪婪算法来考虑各公司为满足的材料量，以车容量和卸货顺序为约束逐步计算出最优化的派遣方案（附表一）。 问题二中，出车后可以掉头，就产生了两种可能减少总运费的运输方式，经过证明可得仅有货物全部卸载完毕后选择最短返程路线可以节省运费，于是在问题一的基础上修改即得到问题二中的最优化派遣方案（附表二）。 问题三中，增加了运输车的种类，并改变了不同类型运输车空载时的运费。于是装载方式多样化。仍以满载为前提，并尽量保证同车货物卸载同地，在问题二的基础上，增加相关约束条件，通过规划得出安排的车辆数为3辆车，一辆6吨位的，两辆8吨位，并得出最优化派遣方案（附表三）。