1.1研究目的及意义

随着物流活动日益精细化和复杂化，使得物流独立成为专业第三方组织，并成为货物运输中的重要力量。在第三方物流的参与下，产品运输已经成为制造商和运输商共同完成的活动。作为制造企业同顾客之间的重要桥梁，运输环节的效率直接影响客户服务水平和配送成本。通过生产与运输的协调，从而降低总配送成本是一条重要的途径。

如何协调运输商与制造商的资源，共同完成运输活动并达到成本最优，逐渐成为了一个值得关注的问题。运输问题可以描述为，从一个或多个供货点向若干需求点的顾客提供运输服务，考虑运输车辆、运输时间、顾客需求等各种条件限制，寻找总体最优的运输方案。

运输问题的起源较早，1941年希奇柯克(Hitchcock)就提出了从多个供应点向多个需求点的运输问题，并提出了相应的数学模型^[1]。Koopmans也曾对该问题提出优化方案，Kantorovich从1942年开始围绕运输问题也进行了大量研究。由此，对运输问题的研究逐渐深入，也对经济和社会的发展起到了很大的推动作用。

经典的运输问题通常考虑在一定的资源条件下（如车辆限制、时间窗限制等），设计从供应点到需求点的订单分配和路线规划方案，并以控制运输成本和运输时间为主要目标。目前对运输问题的研究中，通常将其作为一个独立的环节，而较少考虑其上下环节之间的联系。随着供应链管理理念日渐成熟，并且在实践中得到广泛推广，基于供应链的运输问题已逐渐引起人们的关注，考虑生产、运输和库存之间联系的系统研究已经成为新课题。

本篇论文将运用拉格朗日松弛对运输调度问题进行研究。

1.2国内外研究现状分析

1.2.1运输调度问题研究综述

运输是物流管理中的一个重要环节，运输实现了货物位置的移动。运输问题（Transportation Problem）是制造企业和流通企业的一类及其常见的问题，是运筹学中的一类经典的线性规划问题，也是重要的网络流问题之一。很多学者总结了运输调度问题研究的模式，包括指派问题、最短路问题、最小成本问题，对这些问题列出了模型也给出了详细的计算方法。

由于运输调度问题的复杂性，对运输调度模型与算法的研究一直是国内外学者非常关注的问题之一。1941年Hitchcoch最早提出经典的运输问题^[1]，列出了经典运输问题的常用规划模型，Koopmans于1947年对希奇柯克提出运输问题进行了更深入的研究，之后又有大量的学者对运输模型提出了许多新的模型。一般说来线性规划的求解方法可直接用来求解运输问题，但由于运输调度问题的复杂性，一般的线性规划方法求解运输调度问题要花费很长的时间，结合运输问题自己的特性，人们得到了极为丰富的求解运输问题的方法，其中用的最多的是表上作业法。