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

《物流配送中最优路径规划模拟软件》由会员分享，可在线阅读，更多相关《物流配送中最优路径规划模拟软件（24页珍藏版）》请在装配图网上搜索。

1、物流配送中的最优路径规划模拟软件说明书学校：武汉轻工大学院系：数学与计算机学院专业：信息与计算科学指导教师：王防修小组名称：一苹微歌小组成员：胡鹏 程新强 彭肖飞日期：年 M 日目录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 回溯法的定义回溯法是一种选优搜索法，按选优条件向前搜索，以达到目标。但当探索到某一步时，发现原先选择并不优或达不到目标，就退回一步重新选择，这种走不通就退回再走的技术为回溯法，而满足回溯条件的某

4、个状态的点称为“回溯点”。2.1.2 回溯法的描述可用回溯法求解的问题 P,通常要能表达为：对于已知的由n元组(Xi，X2，,Xn)组成的一个状态空间 E=(Xi,X2，,Xn) I Xj 6 6 , i=1 , 2,，n,给定关于n元组中的一个分量的一 个约束集D,要求E中满足D的全部约束条件的所有 n元组。其中S是分量Xi的定义域，且| S|有限，i=1 , 2,，n。我们称E中满足D的全部约束条件的任一 n元组为问题P的一 个解。解问题P的最朴素的方法就是枚举法，即对E中的所有n元组逐一地检测其是否满足D的全部约束，若满足，则为问题P的一个解。但显然，其计算量是相当大的。我们发现，对于许

5、多问题，所给定的约束集D具有完备性，即i元组(X1,X2，,Xi)满足D中仅涉及到X1, X2,，X的 所有约束意味着j元组(x1，X2，人)一定也满足 D中 仅涉及到Xi , X2,，Xj的所有约束，i =1 ,2,，n。换 句话说，只要存在 0Wj n -1 ,使得（Xi , X2， ）违 反D中仅涉及到Xi , X2，Xj的约束之一，则以（Xi,X2， Xj）为前缀的任何n元组（Xi, X2,，Xj, Xj+,，Xn） 一定也违反D中仅涉及到Xi, X2,，Xi的一个约束，因此， 对于约束集D具有完备性的问题 巳一旦检测断定某个j元组 （Xi, X2,，）违反D中仅涉及Xi, X2,，X

6、j的一个 约束，就可以肯定，以（Xi, X2,，Xj）为前缀的任何 n 元组（Xi, X2,，Xj, Xj4,，Xn）都不会是问题 P的 解，因而就不必去搜索它们、检测它们。回溯法正是针对这类 问题，利用这类问题的上述性质而提出来的比枚举法效率更高 的算法。回溯法首先将问题 P的n元组的状态空间 E表示成一棵 高为n的带权有序树T,把在E中求问题P的所有解转化为在 T中搜索问题P的所有解。树T类似于检索树，它可以这样构 造：设Si中的元素可排成Xi，Xi，,Xi （甲-i） , | =m , i=i , 2,，n。从根开始，让 T的第I层的每一个结 点都有mi个儿子。这m个儿子到它们的双亲的边

7、，按从左到 右的次序，分别带权Xi书（i） , Xi由（2），Xi书（中），i=0 , i,2，n-i。照这种构造方式,E中的一个n元组（Xi,X2，,Xn）对应于T中的一个叶子结点，T的根到这个叶子结点的路径上依次的n条边的权分别为Xi,X2,.,Xn,反之亦然。另外，对于任意的0WiWn-1, E中n元组（Xi，X2，.,Xn）的一个前缀I 元组（Xi，X2，.,Xi）对应于T中的一个非叶子结点，T的根到这个非叶子结点的路径上依次的I条边的权分别为Xi,X2,.,Xi,反之亦然。特别，E中的任意一个n元组的空前缀（），对 应于T的根。因而，在E中寻找问题P的一个解等价于在 T中搜索一 个叶

8、子结点，要求从 T的根到该叶子结点的路径上依次的n条边相应带的n个权Xi,X2,.,Xn满足约束集D的全部约束。在 T中搜索所要求的叶子结点，很自然的一种方式是从根出发，按深度优先的策略逐步深入，即依次搜索满足约束条件的前 缀I元组（Xi）、前缀2元组（Xi , X2）、，前缀I元组 （Xi,X2,.,Xj ,，直至ij i=n 为止。在回溯法中，上述引入的树被称为问题P的状态空间树；树T上任意一个结点被称为问题P的状态结点；树 T上的任意一个叶子结点被称为问题P的一个解状态结点；树 T上满足约束集D的全部约束的任意一个叶子结点被称为问题P的一个回答状态结点，它对应于问题P的一个解。2.1.3

9、 回溯法的基本思想（I）针对所给问题，定义问题的解空间；（2）确定易于搜索的解空间结构；（3）以深度优先方式搜索解空间，并在搜索过程中用剪枝函数避免无效搜索。用回溯法解题的一个显著特征是在搜索过程中动态产生问题 的解空间。在任何时刻，算法只保存从根结点到当前扩展结点的 路径。如果解空间树中从根结点到叶结点的最长路径的长度为 h(n),则回溯法所需的计算空间通常为 O(n)。而显式地存储整个 解空间则需要O(2n)或O(n!)内存空间.2.1.4 回溯法在TSP问题上的应用旅行商问题的回溯算法可作为类 Traveling 的一个成员。在其 他例子中，有一个成员函数：Backtrack与T S P

10、。前者是一个保护 或私有成员，后者是一个共享成员。函数G .T S P ( v )返回最少耗费旅行的花费，旅行自身由整型数组 v返回。若网络中无旅行， 则返回Noedge。Backtrack在排列空间树中进行递归回溯搜索，T SP是其一个必要的预处理过程。TSP假定x (用来保存到当前节点的 路径的整型数组)，best x (保存目前发现的最优旅行的整型数组)， c c (类型为T的变量，保存当前节点的局部旅行的耗费)，best c (类型为T的变量，保存目前最优解的耗费)已被定义为Traveling中的静态数据成员。函数Backtrack见下。它的结构与函数 Perm相同。当i=n时，处在

11、排列树的叶节点的父节点上，并且需要验证从Xn到Xn有一条边，从Xn到起点Xi也有一条边。若两条边都存在，则发现了一个新旅行。 在本例中，需要验证是否该旅行是目前发现的最优旅行。若是，则将 旅行和它的耗费分别存入 best x与best c中。当in是顶i和顶点j之间的距离所组成的距离矩阵,TSP问题就是求出一条通过所有顶点且每个顶点只通过一次的具有最短距离的回路。若dj=dji(i ?j),称为对称TSP问题，否则称为非对称TSP问题。若对于城市 W=(V1, V2,vQ (Vi, V2,.,Vn)的一个访问顺序为 T = E (ti，t2，t3，.,tn),其中 ti 6 V = 1 ,?,

12、 n,且 tn=ti,则TSP问题的数学模型为：mink = E d (ti ,ti+) (i=1,，n),其 中,d (ti,ti中)表示顶点ti和顶点J之间的距离.(3)遗传算法的基本流程：2.2.5 遗传算法的总体设定(1)参数编码和初始群体设定：一般来说，遗传算法对解空间的编码大多采用二进制编码形式，但对TSP-类排序问题，采用对访问城市序列进行排列组合的方法编码，即某个巡回路径的染色体个体是该巡回路径的城市序列。针对TSP问题，编码规则通常是取n进制编码，即每个基因仅从 1到n 的整数里面取一个值，每个个体的长度为 n, n为城市总数。我们定 义一个s -t大小的pop矩阵来表示群体

13、，针对30个城市的TSP 问题，这里t取值31。即矩阵每一行的前30个元素表示经过的城市 编号，最后一个元素表示经过这些城市要走的距离。(2)适应度函数设计：在TSP的求解中，用距离的总和作为适应度函数来衡量求解结果 是否最优。在pop矩阵中每一行表示经过的距离的最后一个元素作 为适应度函数。(3)选择算子：选择就是从群体中选择优胜个体、淘汰劣质个体的操作，它是建 立在群体中个体适应度评估基础上。这里采用方法是最优保存方法。算法就是首先将群体中适应度最大的 k个个体直接替换适应度最小 的k个个体。(4)交叉算子：才交叉算子在遗传算法中起着核心的作用，它是指将个体进行两两 配对，并以交叉概率Pc

14、把配对的父代个体加以替换重组而生成新个体 的操作。这里采用的方法是有序交叉法.有序交叉法实现的步骤是：步骤1:随机选取两个交叉点；步骤2:两后代先分别按对应位置复制双亲 Xi和X2匹配段中的 两个子串A和B ；步骤3.在对应位置交换双亲匹配段以外的城市，如果交换后，后代中的某一城市与子串中的城市重复，则将该城市取代子串B和A中 的城市具有相同位置的新城市 .直到与子串A中的城市均不重复为 止。XI 士。 xn r e8TIII 1S45O I7T3-1N113O2o 5X 1 h =X2二日1 4 17SAes o丁3仝11QO s2 匕El rF 诙 X 广从图可知，有序交叉算子能够有效地继

15、承双亲的部分基因成分，达到了进化过程中的遗传功能，使该算法并不是盲目搜索，而是趋向于使群体具有更多的优良基因，最后实现寻优的目的。(5)变异算子：变异操作是以变异概率 Pm对群体中个体串某些基因位上的基因值作变动，若变异后 子代的适应度值更加优异，则保留子代染色体， 否则，仍保留父代染色体。2.3模拟退火算法2.3.1 模拟退火算法的原理模拟退火算法(Simulated Annealing, SA)来源于固体退火原理，将固体加温至充分高，再让其徐徐冷却，加温时，固体内部粒子随温升变为无序状，内能增大，而徐徐冷却时粒子渐趋有序，在每个温度都达到平衡态，最后在常温时达到基态，内能减为最小。根据_E

16、Metropolis准则，粒子在温度T时趋于平衡的概率为e ,其中E为 温度T时的内能，AE为其改变量，k为Boltzmann常数。用固体退 火模拟组合优化问题，将内能E模拟为目标函数值f,温度T演化成控制参数t,即得到解组合优化问题的模拟退火算法：由初始解i和控制参数初值t开始，对当前解重复“产生新解-计算目标函数差一 接受或舍弃”的迭代，并逐步衰减t值，算法终止时的当前解即为所 得近似最优解，这是基于蒙特卡罗迭代求解法的一种启发式随机搜索 过程。退火过程由冷却进度表(Cooling Schedule)控制，包括控制参 数的初值t及其衰减因子引、每个t值时的迭代次数L和停止条件So 2.3.

17、2模拟退火算法的模型模拟退火算法可以分解为解空间、目标函数和初始解三部分。模拟退火的基本思想:(1)初始化：初始温度 T(充分大)，初始解状态 S(是算法迭代起点)，每个T值的迭代次数L; (2)对k=1,，L 做第(3)至第6步；(3)产生新解S; (4)计算增量 VClSACC), 其中C(S)为评价函数；(5)若巴0,然后转第2步。 算 法 对 应 动 态 演 示 图： 模拟退火算法新解的产生和接受可分为如下四个步骤：第一步是由一个产生函数从当前解产生一个位于解空间的新解； 为便于后续的计算和接受，减少算法耗时，通常选择由当前新解经过 简单地变换即可产生新解的方法，如对构成新解的全部或部

18、分元素进 行置换、互换等，注意到产生新解的变换方法决定了当前新解的邻域 结构，因而对冷却进度表的选取有一定的影响。第二步是计算与新解所对应的目标函数差。 因为目标函数差仅变 换部分产生，所以目标函数差的计算最好按增量计算。事实表明，对 大多数应用而言，这是计算目标函数差的最快方法。第三步是判断新解是否被接受，判断的依据是一个接受准则，最 常用的接受准则是Metropolis准则：若曾0则接受s作为新的当前 解S ,否则以概率e接受S作为新的当前解S。第四步是当新解被确定接受时，用新解代替当前解，这只需将当 前解中对应于产生新解时的变换部分予以实现，同时修正目标函数值即可。此时，当前解实现了一次

19、迭代。可在此基础上开始下一轮试验。 而当新解被判定为舍弃时，则在原当前解的基础上继续下一轮试验。模拟退火算法与初始值无关，算法求得的解与初始解状态S(是算法迭代的起点)无关；模拟退火算法具有渐近收敛性，已在理论上 被证明是一种以概率l收敛于全局最优解的全局优化算法；模拟退 火算法具有并行性。2.3.3 模拟退火算法 的 简单应用作为模拟退火算法应用，讨论货郎担问题(Traveling SalesmanProblem,简记为TSP):设有n个城市，用数码1,n代表。城市i 和城市j之间的距离为d(i,j)i, j=1,n.TSP问题是要找遍访每个域市 恰好一次的一条回路，且其路径总长度为最短。求

20、解 TSP的模拟退火算法模型可描述如下： 解空间 解空间S是遍访每个城市恰好一次的所有回路，是 1 ,，n的所有循环排列的集合，S中的成员记为(Wi,w2,.,Wn),并记Wy=Wi 。 初始解可选为(1 , , n)目标函数此时的目标函数即为访问所有城市的路径总长度或称为代价函数： 我们要求此代价函数的最小值。新解的产生：随机产生1和n之间的两相异数k和m,若k设图最姮时 间.植M车辆按最姮时间规划线路 在界面上行强7.3 界面设计8解决堵车问题模块设计说明 8.1功能在配送过程中可模拟前方行进路线堵车事件，软件能够绕开堵车 路段动态规划配送路线。8.2功能流程图8,3界面设计9未解决的问题

21、1 .客户的地址过于密集甚至覆盖无法进行精准的规划。2 .用人工智能算法得到的是最优近似解不是最优解。10参考资料(1)F G lover. Future paths for integer programming andlinks 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)王7.智能优化算法及其应用M.北京：清华大学出版社.2001:32-33.(5)田贵超，黎明，韦雪洁.旅行商问题(TSP)的几种求解方法J.计算机仿真:2006.23(8):153-157.