第八章：CPLEX在ITS中应用.pdf

CPLEX在ITS中的应用  一、智能交通中最短路问题的概述 最短路问题是网络理论解决的典型问题之一， 可用来解决配送路径选择、管路铺设、线路安装、 厂区布局和设备更新等实际问题。 定义：给定一个赋权有向图，即给了一个有向 图G= （V，A，W），对A中每一个弧aij = （vi， vj）相应地在W中有权w （a ）=w ，又给定G中 ij ij 两个顶点v ，v 。设P是G中从v 到v 的一条路， s t s t 定义路P的权是P中所有弧的权之和，记为W （P）。 最短路问题就是要在所有从v 到v 的路中，求一 s t 条权最小的路，即求一条从v 到v 的路P*，，使： s t W （P*）=min W （P），称P*是从v 到v 的最短路。 s t 1  例1. 在纵横交错的公路网中，货车司机希 望找到一条从一个城市到另一个城市的最 短路。假设下面的图表示的是该公路网， 节点表示货车可以停靠的城市，弧上的权 表示两个城市之间的距离（百公里）。那 么，货车从城市A出发到达城市I，如何选 择行驶路线，使所经过的路程最短？ 2 3 第二节、最短路问题的数学模型 运筹学中求解方法： 1.Dijkstra算法 它是用于解决非负权网络中寻找一个指定点到其他 点的最短路的最好方法。 基本思想是：采用标号法 2.PDM算法 能够解决有负权的网络 3.逐次逼近法 4.Floyd算法 4 优化数学模型的建立 分析  1.已知是什么？  2.目标是什么？  3.约束有哪些？  4.决策变量应该如何选择？结合决策变量如何用 数学语言表示目标函数和约束条件？ 5 优化数学模型的建立 1.已知是什么？  一个有向的网络图，具体来说就是：  节点：数量；  弧：节点到节点间的弧；  弧长：每条弧的弧长；  起始点；  目的点。 6 优化数学模型的建立 2. 目标是什么？  目标：起点到终点的距离最短。 3.约束有哪些？  需要找的从起点到终点的一条路。 7 优化数学模型的建立 4.决策变量应该如何选择？结合决策变量如 何用数学语言表示目标函数和约束条件？  思路一：以每条路为决策变量，需要定义 每条路。（不推荐）  思路二：以每条弧是否选择为决策变量； 目标函数则令所有选择的弧长最小；约束 需要是所有选择的弧要连成一条路径。