限制按车辆数量有单车货物有多车货物按车辆类型单车型货物多车型货物按优化目标按品种多少有单目标有多目标有单品种有多品种兰州交通大学毕业设计论文动态规划法是运筹学的个分枝，它是求解多阶段决策过程的最优化的种数学方法。大约产生于世纪年代初，美国数学家贝尔曼等人根据类多阶段问题的特点，把多阶段决策过程转化为系列互相联系的单阶段决策问题，然后进行逐个求解。与此同时他提出了解决这类问题的最优性原理，研究了很多实际问题，从而创建了解决最优化问题的种新方法动态规划法。虽然动态规划法主要用于求解以时间划分阶段的动态过程优化问题，但些与时间无关的静态规划如线形规划或非线形规划，只要人为引进时间因素后，把它们看成多阶段过程，也可以用动态规划方法求解。在求解最短路径库存管理资源分配设备更新排序装载等问题时，用动态规划方法非常方便。近几十年来，动态规划在理论方法和应用等方面都取得了很大进展，并在工程技术经济工业生产与企业管理军事工程等领域得到了广泛的应用。动态规划法的基本概念多阶段决策问题多阶段决策过程，是指这样类特殊的活动过程问题可以按时间顺序分解成若干相互联系的阶段，在每个阶段都要做出决策，全部过程的决策是个决策序列。要使整个活动的总体效果达到最优的问题，称为多阶段决策问题。决策过程的分类阶段通常用时间表示，在各个时间段，采用不同的决策，即决策随时间而变动，这就是动态的含义。动态规划就是要在时间的推移过程中，在每个时间阶段选择适当的决策，以便整个系统达到最优。根据过程的时间变量是离散的还是连续的，决策过程可分为离散时间决策过程即多阶段决策过程和连续时间决策过程根据过程的演变是确定的还是随机的，决策过程可分为确定性决策过程和随机性决策过程，其中应用最为广泛的是确定性多阶段决策过程。动态规划模型的基本要素个多阶段决策过程最优化问题的动态规划模型通常包含以下要素阶段阶段是对整个过程的自然划分。通常根据时间顺序或空间特征来划分阶段，以便按阶段次序解决优化问题。描述阶段的变量称为阶段变量，常用表示。阶段的划分般是根据时间和空间的自然特征来划分的。状态兰州交通大学毕业设计论文状态表示每个阶段开始时过程所处的自然状况。它应该能够描述过程的特征并且具有无后向性，即当阶段的状态给定时，这个阶段以后过程的演变与该阶段以前各阶段的状态无关，即每个状态都是过去历史的个完整总结。通常还要求状态是直接或间接可以观测的。描述状态的变量称为状态变量，常用表示表示第阶段的状态变量。决策当个阶段的状态确定后,可以做出各种选择从而演变到下个阶段的个状态，这种选择手段称为决策，在最优控制问题中也称为控制。描述决策的变量称为决策变量，常用表示第阶段当状态变量处于时的决策变量。策略策略是个按顺序排列的决策组成的集合。可供选择的的策略有定范围，此范围称为允许策略集合，用表示。从允许策略集合中找出达到最优效果的策略称为最优策略。状态转移方程状态转移方程是确定过程由个状态到另个状态的演变过程。在确定性决策过程中，旦阶段的状态和决策己知，则下个阶段的状态便完全确定。可用状态转移方程表示这种演变规律。指标函数和最优值函数指标函数是用来衡量过程优劣的种数量指标，它是定义在全过程和所有后部子过程上确定的数量函数，常用，表示。最优值函数就是指标函数的的最优值，记为，它表示从第阶段的状态开始到阶段的终止状态的过程，采取最优策略所得到的指标函数。动态规划的基本思想般将前文提到的具有明显的阶段划分和状态转移的动态规划称为标准动态规划。这种标准动态规划是在研究多阶段决策问题时推导出来的，具有严格的数学形式，适合进行理论分析。在实际应用中，许多问题的阶段划分并不明显，这时如果刻意地划分阶段反而更麻烦。般来说，只要该问题可以划分成规模更小的子问题，并且原问题的最优解中包含了子问题的最优解，就可以考虑用动态规划解决。动态规划的是实质是分治思想和解决冗余。动态规划是种将问题实例分解为更小的相似的子问题，并存储子问题的解而避免计算重复的子问题，以解决最优化问题的算法策略。动态规划法所针对的问题般都有个显著的特征，即它所对应的子兰州交通大学毕业设计论文问题树中的子问题呈现大量重复。动态规划法的关键在于，对于重复出现的子问题，只在第次遇见时加以求解，并把答案保存起来，以后再遇到时可直接引用，不必重新求解。动态规划的步骤动态规划般包括如下四个步骤划分阶段按照问题的时间或空间特征，把问题分为若干个阶段。这若干个阶段必须是有序或者可以排序的即无后向性，否则问题就无法用动态规划法求解。选择状态将问题发展到各个阶段时所处的各种客观情况用不同的状态表示出来。同样，状态的选择要满足无后向性。确定决策并写出状态转移方程写出规划方程包括边界条件动态规划的基本方程是规划方程的通用形式化表达式。用动态规划法解决实际问题时，通常按照以下几个步骤进行分析最优解的性质，并描述其结构特征。递归地定义最优解。以自底向上的方式或自顶向下的记忆化方法计算出最优值。根据计算最优值时得到的信息，构造个最优解。如设车辆的额定载重为，可用于配送种不同的货物，货物的重量分别为。每种货物分别对应于个价值体系，用表示，它表示货物价值运费等。设表示第种货物的装入数量，则用动态规划方法求解的具体步骤如下第步装入第种货物件，其最大价值为其中方括号表示取整数。第二步装入第种货物件，其最大价值为其中，第步装入第种货物件，其最大价值为兰州交通大学毕业设计论文其中，配送车辆路径的选择配送车辆路径问题的描述和分类配送车辆路径问题的描述车辆路径问题最早是由和于年首次提出，它是指定数量的客户，各自有不同数量的货物需求，配送中心向客户提供货物，由个车队负责分送货物，组织适当的行车路线，目标是使得客户的需求得到满足，并能在定的约束下，达到诸如路程最短成本最小耗费时间最少等目的。配送车辆路线问题般研究的是在配送中心及用户位置均已知资源及运输能力充分各用户需求量已知的前提下，如何合理高效低成本的解决分配与运送的问题，也就是说如何将货物从配送中心按照定的要求发送到若干个用户点。配送方案应该包括两个相关的环节有哪些用户要被分配到条回路上，即有哪些用户的货物应该安排在同辆车上每条配送路线上用户的连接顺序。配送车辆路线问题的最优解实际上是个效率最高的运输方案，它应明确的规定应派出的车辆型号车辆数以及每辆车的具体行车路线。实施这配送方案，即可以满足用户的需求，又可以使总的运输行程最短。配送车辆路径问题的分类配送路径分为以下三类，如图。图配送车辆路径问题分类图直送式配送运输直送式配送运输，是指个供应点对应个客户的专门送货。从物流优化的角度配送路径直送式配送配送式配送分送式配送兰州交通大学毕业设计论文看，直送式客户的基本条件是其需求量接近于或大于可用车辆的额定载重量，需专门派辆或多辆车次或多次送货。因此，直送情况下，货物的配送追求的多是多装快跑，选择最短配送线路，以节约时间费用提高配送效率。分送式配送运输分送式配送运输，是指由个供应点对多个客户的共同送货。其基本条件是同条线路上所有客户的需求量总和不大于辆车的额定载重量。送货时，有辆车装着所有客户的货物，沿着条精心选择的最佳线路依次将货物送到各个客户手中，这样既保证按时按量将用户需要的货物及时送到，有节约了车辆，节省了费用，缓解了交通紧张的压力，并减少了运输对环境造成的污染。配送式配送运输配送式配送运输，是指由多个供应点向客户的送货运输。它的宗旨是将货物从多个供应点分别送到多个客户手中，即满足客户对货物的配送需要，有满足各供应点存出货要求，并最终做到费用最省。直送式配送直送式客户的基本条件是其需求量接近或大于可用车辆的额定载重量，需派辆或多辆车次或多次送货。般线路的优化是指在忽略车速和不同道路条件车辆运行费用差别的前提下，采用额定载重量相同的车辆求出行程最短的路线作为最经济的运行路线。直送问题的物流优化，主要是寻找物流网络中的最短线路问题。最短路问题是线路优化模型理论中最为基础的问题之，也是解决其他些线路优化问题的有效工具。连通图的最短路径问题，即求两个顶点间长度最短的路径。其中路径长度不是指路径上边数的总和，而是指路径上各边的权值总和。路径长度的具体含义取决于边上权值所代表的意义，如费用影响等都可以。对最短路径问题的描述为假设有个节点和条弧的连通图并且图中的每条弧,都有个长度或者费用，则最短路径问题为在连通图,中找到条从节点到节点距离最短或费用最低的路径。用数学方法表达是连通图且长度矩阵,∣目标函数,兰州交通大学毕业设计论文在考虑使用最短路径求解时，未来能够得到合理的，正确的解，问题模型般需要满足定的假设条件。两点之间的弧线距离为整数在现有的算法下，该假设基本已经不需要考虑。在连通图中，从任何个端点到其他所有的端点都有直接的路径，如果存在不直接相连的端点对，则可以在它们之间加上个极大的距离，例如∞，表示它们之间是不可能最为个备选方案。连通图的所有距离为非负。连通图是有方向性的。上面这些假设条件对于绝大部分算法要求的，只有些特殊的算法，这些假设可能是多余的。对工程实际的研究和抽象，在最短路问题中有种基本原型，分别是连通图,中，从指定起始点到指定目标点之间的最短路径。连通图,中，从指定起始点到其余所有节点之间的最短路径。连通图,中，所有任意两点之间的最短路径。连通图,中，经过个节点最短路径。求解此类最短路径问题，主要有下面几种算法算法。逐次逼近算法。算法等等。本文主要对算法进行介绍。在年提出按路径长度的递增次序，逐步产生最短路径的算法。该算法可以用于求解任意指定两点,之