物流配送中的最优路径规划模拟软件.doc

《物流配送中的最优路径规划模拟软件.doc》由会员分享，可在线阅读，更多相关《物流配送中的最优路径规划模拟软件.doc（25页珍藏版）》请在三一办公上搜索。

1、物流配送中的最优路径规划模拟软件说明书 学校：武汉轻工大学院系：数学与计算机学院 专业：信息与计算科学 指导教师： 小组名称： 小组成员：日期：_年_月_日目录1引言-12算法思路-23总体设计-154系统出错处理设计-175客户数据生成模块设计说明-186行车路径最短模块设计说明-187行车时间最短模块设计说明-198解决堵车问题模块设计说明-209未解决的问题-2110参考资料-211引言1.1编写目的在B2C农产品电子商务物流配送时，物流车装载当日需要配送的货品从仓库出发，按照事先规划好的最优配送路径为每一个客户进行配送，最后返回仓库。物流配送模拟系统就是在配送之前需要根据客户的配送地址

2、间线路间距、经验路况做分析计算出一条最优配送路径。在配送过程中，如果某路段堵车，物流配送模拟系统需要动态调整配送路线。1.2背景说明设计一个物流配送中的最优路径规划模拟软件，解决物流配送过程中路程最短，时间最短以及堵车后重新规划等问题，并在软件的界面上模拟车辆的运行。随着市场经济的发展和物流技术专业化水平的提高，物流配送业得到了迅猛发展。配送路径的选择是否合理，对加快配送速度、提高服务质量、降低配送成本及增加经济效益都有较大影响。配送路径的优化问题是物流配送系统的一个主要问题，物流配送路径的优化就是以最低的运营成本，最快捷的响应速度、最短的配送运输时间，把货物运至用户手中，而后两个指标与第一个

3、指标之间存在着一定的制约关系，无法达到全体的最优，因此严格地讲，这是一个多目标的优化问题。1.3定义 T S P（Traveling Salesman Problem）:旅行商问题 Backtrack：回溯 GA（Genetic Algorithm）：遗传算法 SA(Simulated Annealing)：模拟退火算法2算法思路2.1回溯算法2.1.1回溯法的定义 回溯法是一种选优搜索法，按选优条件向前搜索，以达到目标。但当探索到某一步时，发现原先选择并不优或达不到目标，就退回一步重新选择，这种走不通就退回再走的技术为回溯法，而满足回溯条件的某个状态的点称为“回溯点”。2.1.2 回溯法的描

4、述 可用回溯法求解的问题P，通常要能表达为：对于已知的由n元组组成的一个状态空间E= ，i=1，2，n，给定关于n元组中的一个分量的一个约束集D，要求E中满足D的全部约束条件的所有n元组。其中是分量的定义域，且 | 有限，i=1，2，n。我们称E中满足D的全部约束条件的任一n元组为问题P的一个解。解问题P的最朴素的方法就是枚举法，即对E中的所有n元组逐一地检测其是否满足D的全部约束，若满足，则为问题P的一个解。但显然，其计算量是相当大的。 我们发现，对于许多问题，所给定的约束集D具有完备性，即i元组满足D中仅涉及到，的所有约束意味着j元组（，）一定也满足D中仅涉及到，的所有约束，i =1，2，

5、n。换句话说，只要存在0jn-1，使得（，）违反D中仅涉及到，的约束之一，则以（，）为前缀的任何n元组（，）一定也违反D中仅涉及到，的一个约束，因此，对于约束集D具有完备性的问题P，一旦检测断定某个j元组（，）违反D中仅涉及，的一个约束，就可以肯定，以（，）为前缀的任何n元组（，）都不会是问题P的解，因而就不必去搜索它们、检测它们。回溯法正是针对这类问题，利用这类问题的上述性质而提出来的比枚举法效率更高的算法。 回溯法首先将问题P的n元组的状态空间E表示成一棵高为n的带权有序树T，把在E中求问题P的所有解转化为在T中搜索问题P的所有解。树T类似于检索树，它可以这样构造： 设中的元素可排成(1)

6、，(2)，(-1)，| =，i=1，2，n。从根开始，让T的第I层的每一个结点都有个儿子。这个儿子到它们的双亲的边，按从左到右的次序，分别带权(1) ，(2) ，() ，i=0，1，2，n-1。照这种构造方式，E中的一个n元组对应于T中的一个叶子结点，T的根到这个叶子结点的路径上依次的n条边的权分别为，反之亦然。另外，对于任意的0in-1，E中n元组的一个前缀I元组对应于T中的一个非叶子结点，T的根到这个非叶子结点的路径上依次的I条边的权分别为，反之亦然。特别，E中的任意一个n元组的空前缀（），对应于T的根。 因而，在E中寻找问题P的一个解等价于在T中搜索一个叶子结点，要求从T的根到该叶子结点

7、的路径上依次的n条边相应带的n个权满足约束集D的全部约束。在T中搜索所要求的叶子结点，很自然的一种方式是从根出发，按深度优先的策略逐步深入，即依次搜索满足约束条件的前缀1元组（）、前缀2元组（，）、，前缀I元组，直到i=n为止。 在回溯法中，上述引入的树被称为问题P的状态空间树；树T上任意一个结点被称为问题P的状态结点；树T上的任意一个叶子结点被称为问题P的一个解状态结点；树T上满足约束集D的全部约束的任意一个叶子结点被称为问题P的一个回答状态结点，它对应于问题P的一个解。2.1.3回溯法的基本思想 (1)针对所给问题，定义问题的解空间； (2)确定易于搜索的解空间结构； (3)以深度优先方式

8、搜索解空间，并在搜索过程中用剪枝函数避免无效搜索。 用回溯法解题的一个显著特征是在搜索过程中动态产生问题的解空间。在任何时刻，算法只保存从根结点到当前扩展结点的路径。如果解空间树中从根结点到叶结点的最长路径的长度为h(n)，则回溯法所需的计算空间通常为O(n)。而显式地存储整个解空间则需要O(2n)或O(n!)内存空间.2.1.4回溯法在TSP问题上的应用 旅行商问题的回溯算法可作为类Traveling 的一个成员。在其他例子中，有一个成员函数：Backtrack与T S P。前者是一个保护或私有成员，后者是一个共享成员。函数G .T S P ( v )返回最少耗费旅行的花费，旅行自身由整型数

9、组 v 返回。若网络中无旅行，则返回No edge。Backtrack在排列空间树中进行递归回溯搜索， T S P是其一个必要的预处理过程。TSP假定x（用来保存到当前节点的路径的整型数组），best x（保存目前发现的最优旅行的整型数组），c c（类型为T的变量，保存当前节点的局部旅行的耗费），best c（类型为T的变量，保存目前最优解的耗费）已被定义为Traveling中的静态数据成员。 函数Backtrack见下。它的结构与函数Perm相同。当i=n 时，处在排列树的叶节点的父节点上，并且需要验证从到有一条边，从到起点 也有一条边。若两条边都存在，则发现了一个新旅行。在本例中，需要验证

10、是否该旅行是目前发现的最优旅行。若是，则将旅行和它的耗费分别存入best x与best c中。当in 时，检查当前i-1 层节点的孩子节点，并且仅当以下情况出现时，移动到孩子节点之一：1. 有从 到的一条边（如果是这样的话，定义了网络中的一条路径）；2.路径 的耗费小于当前最优解的耗费。变量cc 保存目前所构造的路径的耗费。每次找到一个更好的旅行时，除了更新best x 的耗费外，Backtrack需耗时O(n- 1 )!)。因为需发生O(n-1)!)次更新且每一次更新的耗费为(n)时间，因此更新所需时间为O(n(n- 1)!)。通过使用加强的条件能减少由Backtrack搜索的树节点的数量。

11、2.2遗传算法2.2.1遗传算法的定义 遗传算法（Genetic Algorithm）是模拟达尔文的遗传选择和自然淘汰的生物进化过程的计算模型，是一种通过模拟自然进化过程搜索最优解的方法，它是由美国Michigan大学J. Holland教授于1975年首先提出来的，并出版了颇有影响的专著Adaptation in Natural and Artificial Systems，GA这个名称才逐渐为人所知，J. Holland教授所提出的GA通常为简单遗传算法（SGA）。 遗传算法是从代表问题可能潜在的解集的一个种群（population）开始的，而一个种群则由经过基因（gene）编码的一定数目

12、的个体(individual)组成。每个个体实际上是染色体(chromosome)带有特征的实体。染色体作为遗传物质的主要载体，即多个基因的集合，其内部表现（即基因型）是某种基因组合，它决定了个体的形状的外部表现，如黑头发的特征是由染色体中控制这一特征的某种基因组合决定的。因此，在一开始需要实现从表现型到基因型的映射即编码工作。由于仿照基因编码的工作很复杂，我们往往进行简化，如二进制编码，初代种群产生之后，按照适者生存和优胜劣汰的原理，逐代（generation）演化产生出越来越好的近似解，在每一代，根据问题域中个体的适应度（fitness）大小选择（selection）个体，并借助于自然遗传

13、学的遗传算子（genetic operators）进行组合交叉（crossover）和变异（mutation），产生出代表新的解集的种群。这个过程将导致种群像自然进化一样的后生代种群比前代更加适应于环境，末代种群中的最优个体经过解码（decoding），可以作为问题近似最优解。2.2.2遗传算法的特点 遗传算法是一类可用于复杂系统优化的具有鲁棒性的搜索算法，与传统的优化算法相比，主要有以下特点：（1）遗传算法以决策变量的编码作为运算对象。传统的优化算法往往直接决策变量的实际植本身，而遗传算法处理决策变量的某种编码形式，使得我们可以借鉴生物学中的染色体和基因的概念，可以模仿自然界生物的遗传和进化

14、机理，也使得我们能够方便的应用遗传操作算子。（2）遗传算法直接以适应度作为搜索信息，无需导数等其它 辅助信息。（3）遗传算法使用多个点的搜索信息，具有隐含并行性。（4）遗传算法使用概率搜索技术，而非确定性规则。2.2.3遗传算法求解TSP问题的实现（1）编码方法：对于一个TSP问题的城市列表W,假定每个城市的一个访问顺序为T=,规定每访问完一个城市,就从城市列表中将该城市去掉,则用第i(i=1,2,3,n)个访问的城市在所有未访问城市列表W中的对应位置序号(i = 1，2，3,n+1)就可表示具体访问哪个城市,如此这样直到处理完W中所有的城市。将全部gi顺序摆列在一起得到一个列表:G=就可表示

15、一条巡回路线 ,它即为遗传算法中的一个个体的基因. 例如:W=(1 2 3 4 5 6 7 8 9 10 11 12 13 14 15),则Path=(8 15 2 10 7 4 3 11 14 6 12 9 5 13 1)对应Chrome=(8 14 2 8 6 3 2 5 7 3 4 3 2 2 1). 这种编码法的优点在于任意的基因型个体都对应着一条有实际意义的巡回路线,因此可使用常规的交叉算子对其进行操作。（2）TSP 问题的数学模型:假设有一个图G=( V ,E),其中V是顶点集,E是边集,设D= 是顶i和顶点j之间的距离所组成的距离矩阵,TSP 问题就是求出一条通过所有顶点且每个顶

16、点只通过一次的具有最短距离的回路。若(i j),称为对称TSP问题,否则称为非对称TSP问题。若对于城市W =的一个访问顺序为T =,其中V = 1 , , n,且 = ,则 TSP 问题的数学模型为:mink = d(i=1,n),其中,d表示顶点和顶点之间的距离.（3）遗传算法的基本流程: 2.2.4遗传算法的总体设定（1）参数编码和初始群体设定:一般来说，遗传算法对解空间的编码大多采用二进制编码形式，但对TSP一类排序问题，采用对访问城市序列进行排列组合的方法编码，即某个巡回路径的染色体个体是该巡回路径的城市序列。针对TSP问题，编码规则通常是取 n 进制编码，即每个基因仅从1到n的整数

17、里面取一个值，每个个体的长度为 n，n为城市总数。我们定义一个s -t 大小的 pop 矩阵来表示群体，针对 30 个城市的TSP问题，这里 t取值31。即矩阵每一行的前30个元素表示经过的城市编号，最后一个元素表示经过这些城市要走的距离。（2）适应度函数设计:在TSP的求解中，用距离的总和作为适应度函数来衡量求解结果是否最优。在 pop矩阵中每一行表示经过的距离的最后一个元素作为适应度函数。（3）选择算子:选择就是从群体中选择优胜个体、淘汰劣质个体的操作，它是建立在群体中个体适应度评估基础上。这里采用方法是最优保存方法。算法就是首先将群体中适应度最大的 k个个体直接替换适应度最小的k个个体。

18、（4）交叉算子:才交叉算子在遗传算法中起着核心的作用，它是指将个体进行两两配对，并以交叉概率把配对的父代个体加以替换重组而生成新个体的操作。这里采用的方法是有序交叉法. 有序交叉法实现的步骤是: 步骤1: 随机选取两个交叉点；步骤2: 两后代先分别按对应位置复制双亲和匹配段中的两个子串和； 步骤3.在对应位置交换双亲匹配段以外的城市,如果交换后, 后代中的某一城市与子串中的城市重复，则将该城市取代子串和中的城市具有相同位置的新城市.直到与子串中的城市均不重复为止。从图可知，有序交叉算子能够有效地继承双亲的部分基因成分，达到了进化过程中的遗传功能，使该算法并不是盲目搜索，而是趋向于使群体具有更多

19、的优良基因，最后 实现寻优的目的。（5）变异算子:变异操作是以变异概率对群体中个体串某些基因位上的基因值作变动，若变异后 子代的适应度值更加优异，则保留子代染色体，否则，仍保留父代染色体。2.3模拟退火算法2.3.1模拟退火算法的原理 模拟退火算法(Simulated Annealing，SA)来源于固体退火原理，将固体加温至充分高，再让其徐徐冷却，加温时，固体内部粒子随温升变为无序状，内能增大，而徐徐冷却时粒子渐趋有序，在每个温度都达到平衡态，最后在常温时达到基态，内能减为最小。根据Metropolis准则，粒子在温度T时趋于平衡的概率为，其中E为温度T时的内能，E为其改变量，k为Boltz

20、mann常数。用固体退火模拟组合优化问题，将内能E模拟为目标函数值f，温度T演化成控制参数t，即得到解组合优化问题的模拟退火算法：由初始解i和控制参数初值t开始，对当前解重复“产生新解计算目标函数差接受或舍弃”的迭代，并逐步衰减t值，算法终止时的当前解即为所得近似最优解，这是基于蒙特卡罗迭代求解法的一种启发式随机搜索过程。退火过程由冷却进度表(Cooling Schedule)控制，包括控制参数的初值t及其衰减因子、每个t值时的迭代次数L和停止条件S。 2.3.2模拟退火算法的模型 模拟退火算法可以分解为解空间、目标函数和初始解三部分。模拟退火的基本思想:(1)初始化：初始温度T(充分大)，初

21、始解状态S(是算法迭代起点)，每个T值的迭代次数L；(2) 对k=1，L做第(3)至第6步；(3) 产生新解；(4) 计算增量=C()-C(S)，其中C(S)为评价函数 ；(5) 若0，然后转第2步。算法对应动态演示图： 模拟退火算法新解的产生和接受可分为如下四个步骤： 第一步是由一个产生函数从当前解产生一个位于解空间的新解；为便于后续的计算和接受，减少算法耗时，通常选择由当前新解经过简单地变换即可产生新解的方法，如对构成新解的全部或部分元素进行置换、互换等，注意到产生新解的变换方法决定了当前新解的邻域结构，因而对冷却进度表的选取有一定的影响。 第二步是计算与新解所对应的目标函数差。因为目标函

22、数差仅变换部分产生，所以目标函数差的计算最好按增量计算。事实表明，对大多数应用而言，这是计算目标函数差的最快方法。 第三步是判断新解是否被接受,判断的依据是一个接受准则，最常用的接受准则是Metropo1is准则: 若0则接受作为新的当前解S，否则以概率接受作为新的当前解S。 第四步是当新解被确定接受时，用新解代替当前解，这只需将当前解中对应于产生新解时的变换部分予以实现，同时修正目标函数值即可。此时，当前解实现了一次迭代。可在此基础上开始下一轮试验。而当新解被判定为舍弃时，则在原当前解的基础上继续下一轮试验。 模拟退火算法与初始值无关，算法求得的解与初始解状态S(是算法迭代的起点)无关；模拟

23、退火算法具有渐近收敛性，已在理论上被证明是一种以概率l 收敛于全局最优解的全局优化算法；模拟退火算法具有并行性。2.3.3模拟退火算法的简单应用 作为模拟退火算法应用，讨论货郎担问题(Traveling Salesman Problem，简记为TSP)：设有n个城市，用数码1,n代表 。城市i和城市j之间的距离为 i, j=1,nTSP问题是要找遍访每个域市恰好一次的一条回路，且其路径总长度为最短。 求解TSP的模拟退火算法模型可描述如下： 解空间 解空间S是遍访每个城市恰好一次的所有回路，是1，n的所有循环排列的集合，S中的成员记为,并记。初始解可选为(1，n) 目标函数 此时的目标函数即为

24、访问所有城市的路径总长度或称为代价函数： 我们要求此代价函数的最小值。 新解的产生：随机产生1和n之间的两相异数k和m，若km，则将变为：。如果是则将变为：上述变换方法可简单说成是“逆转中间或者逆转两端”。也可以采用其他的变换方法，有些变换有独特的优越性，有时也将它们交替使用，得到一种更好方法。 代价函数差 设将变换为 则代价函数差为： 根据上述分析，可写出用模拟退火算法求解TSP问题的伪程序： 模拟退火算法的应用很广泛，可以较高的效率求解最大截问题(Max Cut Problem)、0-1背包问题(Zero One Knapsack Problem)、图着色问题(Graph Coloring

25、 Problem)、调度问题(Scheduling Problem)等等。 2.3.4模拟退火算法的参数控制问题模拟退火算法的应用很广泛，可以求解NP完全问题，但其参数难以控制，其主要问题有以下三点： (1) 温度T的初始值设置问题。温度T的初始值设置是影响模拟退火算法全局搜索性能的重要因素之一、初始温度高，则搜索到全局最优解的可能性大，但因此要花费大量的计算时间；反之，则可节约计算时间，但全局搜索性能可能受到影响。实际应用过程中，初始温度一般需要依据实验结果进行若干次调整。 (2)退火速度问题模拟退火算法的全局搜索性能也与退火速度密切相关。一般来说，同一温度下的“充分”搜索(退火)是相当必要

26、的，但这需要计算时间。实际应用中，要针对具体问题的性质和特征设置合理的退火平衡条件。 (3)温度管理问题。温度管理问题也是模拟退火算法难以处理的问题之一。实际应用中，由于必须考虑计算复杂度的切实可行性等问题，常采用如下所示的降温方式：式中k为正的略小于1.00的常数，t为降温的次数 。3总体设计3.1需求规定3.1.1.生成客户数据1.用户可以在软件界面上随机标注仓库与客户的地址(不少于10个客户)； 2.客户的地址表示采用Window设备坐标系。客户地址间的距离采用设备坐标像素间距模拟，坐标之间行驶速度采用随机算法生成。3.1.2动态路线规划 1.软件可根据用户选择的路径规划策略，如最短路径

27、、最少时间等进行配送路线规划。 2.模拟车辆从仓库出发，沿着规划的配送路线行进，最后返回仓库。在配送过程中可模拟前方行进路线堵车事件，软件能够绕开堵车路段动态规划配送路线。3.2运行环境PC，Visual C+6.0软件开发平台3.3基本设计概念和处理流程3.4结构设计3.4.1结构 3.4.2功能需求与程序的关系3.4.3人工处理过程点击界面作图区以获得站点的编号以及位置坐标数据，设置仓库的位置，设置行车策略（行车路径最短或行车时间最短），设置堵车路线。仓库不存在和堵车路线不存在时，重新输入仓库位置和堵车路线。4系统出错处理设计4.1出错信息5客户数据生成模块设计说明5.1功能 用户可以在物

28、流配送模拟系统软件界面上随机标注仓库与客户的地址（不超过300个），客户的地址表示采用Window设备坐标系。5.2功能流程图5.3界面设计6行车路径最短模块设计说明6.1功能软件可根据用户选择的路径规划策略：行车路径最短进行配送路线规划。模拟车辆从仓库出发，沿着规划的配送路线行进，最后返回仓库。6.2功能流程图6.3界面设计7行车时间最短模块设计说明7.1功能软件可根据用户选择的路径规划策略：行车0时间最短进行配送路线规划。模拟车辆从仓库出发，沿着规划的配送路线行进，最后返回仓库。7.2功能流程图7.3界面设计8解决堵车问题模块设计说明8.1功能在配送过程中可模拟前方行进路线堵车事件，软件能

29、够绕开堵车路段动态规划配送路线。8.2功能流程图8.3界面设计9未解决的问题1客户的地址过于密集甚至覆盖无法进行精准的规划。2用人工智能算法得到的是最优近似解不是最优解。10参考资料(1)F G lover. Future paths for integer programming and links to artificial intelligenceJ.Computer and Operation Research.1986,13:533-549.(2)李大军，张建兰，官运兰，等.旅行商问题的一种插入交叉算子J.计算机工程与应用，2003.39(33):67-69.(3)唐立新.旅行商问题(TSP)的改进遗传算法J.东北大学学报：自然科学版，1999，1:40-43.(4)王凌.智能优化算法及其应用M.北京：清华大学出版社.2001:32-33.(5)田贵超,黎明,韦雪洁.旅行商问题(TSP)的几种求解方法J.计算机仿真:2006.23(8):153-157.