运筹学最短路径精选(九篇)

前言：一篇好文章的诞生，需要你不断地搜集资料、整理思路，本站小编为你收集了丰富的运筹学最短路径主题范文，仅供参考，欢迎阅读并收藏。

第1篇：运筹学最短路径范文

关键词： AutoCAD；Auto LISP；最短路径

Abstract: This paper describes in the CAD platform, using Auto LISP programming language, take a received a cable graphics for example to research on the shortest path problem and how to improve the retrieval speed of the shortest path, and quickly come to retrieve results.Key words: AutoCAD; the Auto the LISP; shortest path

中图分类号：P315.69 文献标识码：A文章编号：2095-2104（2012）

引言

最短路径问题在计算机科学、运筹学、交通工程学、地理信息系统等学科中是一个研究的热点，它是资源分配、线路选择等问题解决的基础，尤其是在诸如地图、车辆调度和路由选择方面有着广泛的应用。基于其具有广泛的应用性，所以本文以一个交通路线的选择为例对其进行了研究，希望能起到抛砖引玉的作用。

1 软件的运行平台及开发语言的简介

AutoCAD是美国Autodesk公司推出的通用计算机绘图软件，它以其强大的绘图功能和良好的开发环境，广泛应用于机械、电子、化工、建筑、测量与勘察等行业。对AutoCAD进行二次开发的手段很多，例如Auto LISP、ADS、ARX、VBA等，本程序使用的是Auto LISP编程语言，它已被嵌入CAD中。Auto LISP具有语法简单、功能强大、易学易用的特点，它的数据类型相当随意，可以组织处理不同长度和结构的数据类型，用户可以按要求和最佳结构设计使用自定义的结构类型数据，而不会感到组织数据结构上的困难。另外，Auto LISP擅长人机交互操作的过程，对用户输入的接受、错误识别、恢复操作等方面的优秀功能，是其它语言难以比及的。

2 程序具体实现

2.1 设计思路

研究最短路径问题，我们不得不提到宽度优先搜索算法（又称广度优先搜索），它是最简便的图的搜索算法之一，这一算法也是很多重要的图的算法的原型。Dijkstra单源最短路径算法和Prim最小生成树算法都采用了和宽度优先搜索类似的思想。

2.1.1在存储扩展成果表时采用分段存储方式，将点号按大小分成四段存储在四个表中，便于在检索点号时只检索其中的一个表即可，缩小检索点范围。

2.1.2设置检索距离，当检索距离大于已找到的终点检索距离后停止检索，避免做无用的检索。

2.1.3程序以起始点到终点的有向线段方向预设优先检索方向，先收索与之方向夹角小的路径，争取最短时间得到终点检索距离值，减小检索范围。

2.1.4在检索存储点号时对存储表采用二分法检索，以提高点号的获取速度。

2.2 程序原代码

(defun c:drj()

(setvar "CMDECHO" 0)

(setq SEHfbl1 nil SEHfbl2 nil SEHfbl3 nil SEHfbl4 nil) ;;设置存储块点点表

(setq lstDZbl1 nil lstDZbl2 nil lstDZbl3 nil lstDZbl4 nil);;设置对照点表

(setq SEHfh (SEHBLPX));;初始化块点点表

(setq QiShiDian (car (entsel "\n选择起始点:")))

(setq SelQSDlst (entget QiShiDian))

(setq SelQSDxyh (cdr (assoc 10 SelQSDlst)))

(setq SelQSDh (fix (last SelQSDxyh)));;起始点点号

(princ "\n您选择的起始点为:")

(princ SelQSDh)

(setq ZhongDian (car (entsel "\n选择目的点:")))

(setq SelZDlst (entget ZhongDian))

(setq SelZDxyh (cdr (assoc 10 SelZDlst)))

(setq SelZDh (fix (last SelZDxyh)));;起始点点号

(princ "\n您选择的目的点为:")

(princ SelZDh)

(command ".zoom" "e")

(alert "程序即将运行,可能需要一点时间,请耐心等候!")

(setq lstDKbl nil);;预置待扩点表

(setq lstJieGuo nil)

(setq finddist 0)

(setq lstTmp nil)

(setq lstKYbltmp nil);;预置扩延临时表

(setq Firstflag 0)

(setq lstTmp (LJDBall SelQSDh));;对起始点扩展

(if (vl-consp lstTmp) (progn;;如果lstTmp不为空表

(setq maini 0)

(repeat (length lstTmp)

(setq mainys (nth maini lstTmp))

(setq mainysb (list SelQSDh mainys))

(if (

(if (and (> mainys SEHfh) (

(if (and (> mainys (* 2 SEHfh)) (

(if (> mainys (* 3 SEHfh)) (setq lstDZbl4 (cons mainysb lstDZbl4)))

(setq lstDKbl (cons mainysb lstDKbl))

(setq maini (+ maini 1))

)

(setq lstDKbl (reverse lstDKbl));;生成待扩点表

(if (vl-consp lstDZbl1) (progn;;如果lstDZbl1(对照点表1)不为空

(setq lstDZbl1 (vl-sort lstDZbl1 (function (lambda (e1 e2) (< (cadr e1) (cadr e2))))));;对表进行排序点号从小到大

))

(if (vl-consp lstDZbl2) (setq lstDZbl2 (vl-sort lstDZbl2 (function (lambda (e1 e2) (< (cadr e1) (cadr e2)))))))

(if (vl-consp lstDZbl3) (setq lstDZbl3 (vl-sort lstDZbl3 (function (lambda (e1 e2) (< (cadr e1) (cadr e2)))))))

(if (vl-consp lstDZbl4) (setq lstDZbl4 (vl-sort lstDZbl4 (function (lambda (e1 e2) (< (cadr e1) (cadr e2)))))))

(setq lstDKbl (QCDFUN lstDKbl));;获得纯正的扩展点表

(while (vl-consp lstDKbl);;循环到lstDKbl为空表为止

(KYFUN lstDKbl SelQSDh);;对lstDKbl进行一次扩延

(setq lstDKbl (QCDFUN lstKYbltmp))

(setq lstDKbl (JJPL SelQSDh SelZDh lstDKbl));;按方向夹角从小到大排序

(setq lstKYbltmp nil)

)

))

(if (vl-consp lstJieGuo) (progn;;如果结果表不为空

(princ "\n起点到目的点最短路径是:")

(princ "\n")

(princ lstJieGuo)

(princ "\n距离为:")

(princ finddist)

))

(if (not (vl-consp lstJieGuo)) (progn;;如果结果表为空

(princ "\n从起点没有路径能到达目的点!!!")

))

(princ)

)

3 结束语

本程序是在CAD平台下开发的，其收索所需线画图的制作和更新都十分便捷，利用此程序对多个中小城市的道路图做收索实验，其最大范围的检索时间在十几秒之内，一般范围的收索均在几秒内完成，因此程序具有较强的实用价值。由于篇幅所限本文仅列出了主程序模块的原代码，有编写繁琐之处敬请批评指正。

参考文献

[1] 康博．中文版AutoCAD2000/2002 Visual LISP开发指南[M]，北京：清华大学出版社，2001.8

[2] 唐亮，等．AutoCAD2002开发教程[M]，北京：北京希望电子出版社，2002.8

[3]（美）Hamdy A.Taha.运筹学导论：初级篇（第8版）[M].北京：人民邮电出版社，2008

第2篇：运筹学最短路径范文

关键词：图论；最短路径；Dijkstra；Floyd；演示系统

中图分类号：TP393 文献标识码：A 文章编号：1009-3044（2016）18-0159-02

图论问题始终渗透整个计算机科学，可以说每个编程者都不可避免地与图打交道，因而图论算法对计算机科学至关重要。它的应用领域非常多。例如，图论可以应用于电路网络分析、运筹学、网络、信息论、控制论以及计算机科学等各个领域。我们知道最短路径问题是网络理论中应用最为广泛的问题之一。而这里介绍的最短路径算法是图论算法中重要的一支。最短路径算法可以解决许多问题，例如：线路安排、管道铺设、路由选择、地址选择、设备更新、广场布局、时变拓扑网络等。我们这里研究的就是最短路径问题的算法，具体指的是迪杰斯特拉（Dijkstra）算法和弗洛伊德（Floyd）算法。这里通过开发一个系统演示程序来生动的阐述迪杰斯特拉（Dijkstra）算法和弗洛伊德（Floyd）算法。该系统演示程序简单易用、清晰明了、界面友好、非常实用。该系统演示程序是在Eclipse和JDK1.6的环境下用java语言开发而成的。它为解决最短路径问题提供了一个简单实用的平台。

1 最短路径问题

定义：我们给定一个带权重的有向图G=（V，E）和权重函数w：ER，该权重函数将每条边映射到实数值的权重上。图中一条路径p=的权重w（p）是构成该路径的所有边的权重之和：w（p）=∑w（vi-1 ， vi） ，i=1，2，3…，k。

假设一条从节点m到节点n的最短路径权重为W（m，n），且W（m，n）计算如下：

①如果存在一条从节点m到节点n的路径，则：W（m，n）=min{w（p）|p是一条从节点m到节点n的路径}；②否则，W（m，n）=∞。

从节点m到节点n的路径p，如果满足w（p）= W（m，n）则该路径p即为从节点m到节点n的最短路径。求从节点m到节点n的最短路径和最短距离的问题就是最短路径问题。

2 最短路径算法

2.1弗洛伊德算法思想

我们使用三重for循环产生一个矩阵来记录每个节点间的最小距离。对于弗洛伊德（Floyd）算法我们使用矩阵Juzhen[i][j]（i，j=1，2，……n+1）存储有向图的权重值。所以，其基本思想为：初始化一个n阶矩阵A（k），其主对角线上的元素初始化为0，非对角线上的元素初始化A（k） [i][j]，其中每一个A（k） [i][j]是节点i到节点j的权重值，k是运算到第几步。算法一开始，我们选择任意两个节点分别作为起始点和终止点，若他们之间有边则取其权重值作为他们的路径长度，若无权重边，则令其路径长度为∞，再有k=0时，我们初始化A（k）[i][j]，此时A（0）[i][j]=Juzhen[i][j]，将路径上的节点加入集合S中，之后再选择不在集合S中但能构成最短路径的节点，使其加入集合S，如果在i节点和j节点之间增加了中间节点后，使得节点i到节点j的路径比A（k） [i][j]小，就用新的权重值去更新A（k） [i][j]。

因此，弗洛伊德（Floyd）算法步骤如下：

（1）当k=0时，A（0）[i][j]= Juzhen[i][j]； 其中Juzhen[i][j]为邻接矩阵

（2）当k=i+1，i+2，…，j时，A（k）[i][j]=min{A（k-1） [i][j]，A（k-1） [i][k]+A（k-1） [k][j]}

其中A（k）[i][j]表示节点点vi 到vj ， 中间节点的不大于k的最短路径的长度，这里求的是中间节点的不大于n的最短路径的长度即A（n）[i][j]。

因而，其算法可以描述为：

（1）令D[i][j]=A[i][j]

（2）for（k=1；k

for（i=1；i

for（j=1；j

if（D[i][j]> D[i][k]+ D[k][j]）

{D[i][j]=D[i][k]+ D[k][j]}

（3）算法结束后矩阵D存储了所有节点之间的最短路径值。

2.2 迪杰斯特拉算法的思想

Dijkstra算法解决的是带权重的有向图上单源点最短路径的问题。该算法要求所有边的权重都为非负值。Dijkstra算法把图中所有的节点分为两组：设集合S表示已经求出的最短路径上的节点的集合；集合T=V-S表示在集合V中而在节点S之外的所有的节点的集合。然后把集合T中节点按权值非减的次序排序，并按此顺序依次加入到集合S里。除此之外，还要满足如下两个条件：第一，从出发点v0到集合S中每一个节点的最短路径长度A（k）[i][j]都应该小于或者等于从节点v0到集合T中所有节点的权重值也即最短路径长度；第二，集合S和集合T都对应一个距离值。S中的节点表示的距离是从出发点v0到该集合中每一个节点的最短路径长度，集合T中的节点表示从出发点v0到集合T中所有的节点且只经过集合S中节点作为中间节点的最短路径长度。因此，迪杰斯特拉算法可描述为：

设置辅助数组dist，其中每个分量dist[k] 表示 当前所求得的从源点到其余各顶点k的最短路径。

（1）S = {v0}；//顶点v0为源点

（2）设置集合V-S中各顶点的初始距离值；

（3）while （集合S中顶点数

{在集合V-S中选择距离最小的顶点vj；S=S+{vj}；

调整集合VS中顶点的距离值；}

3 最短路径算法图形化演示程序检验

下面通过一个实例检验系统演示程序的正确性。

实例：如图1所示，求一条从节点A到节点C的最短路径，并求出其权重值。

具体操作步骤是：①运行系统；②点击新结点按钮和结点连线按钮，然后在画布上用鼠标点击构造结点和连线；③双击结点输入结点名，双击连线输入权重值，以此构造出图1；④选择始点为A，终点为B，选择使用的算法（迪杰斯特拉算法或弗洛伊德算法）；⑤点击激活按钮后，点击开始按钮，结果如图2所示；⑥点击算法展示按钮会出现迪杰斯特拉算法和弗洛伊德算法的展示选择界面；⑦点击概念展示按钮会出现迪杰斯特拉算法和弗洛伊德算法的概念选择界面；⑧在算法展示界面和概念展示界面点击相应的按钮会弹出与此相符的PPT文件进行展示。

4 结论

在了解图论最短路径的问题的算法（迪杰斯特拉（Dijkstra）算法和弗洛伊德（Floyd）算法）、概念和原理的基础上，开发了一个算法图形化演示程序，并对改程序进行了正确性的验证。这里开发的算法系统演示程序生动形象地阐述了迪杰斯特拉（Dijkstra）算法和弗洛伊德（Floyd）算法的概念和原理，并通过画图的方式简化了操作。该系统演示程序简单易用、清晰明了、界面友好、非常实用。它为解决最短路径问题提供了一个简单实用的平台，这样的研究是有积极意义的。

参考文献：

[1] 田丰，马仲蕃.图与网络流理论[M].北京：科学出版社，1987.

[2] 徐凤生.求最短路径的新算法[J].计算机工程与科学，2006，2.

[3] 魏文红，李清霞，蔡昭权.一种基于桶结构的单源最短路径算法[J].计算机工程与科学，2012，4（34）：77-81

[4] 王树西，吴政学.改进的Dijkstra 最短路径算法及其应用研究[J].计算机科学，2012，5（39）：223-228

[5] 朱福喜.面向对象与Java程序设计[M]. 北京：清华大学出版社，2008.

[6] 朱福喜.Java编程技巧与开发实例[M]. 北京：清华大学出版生，2004.

[7] 王昆仑，李红.数据结构与算法[M]. 北京：中国铁道出版社，2006.

[8] 侯风巍.数据结构要点精细[M]. 北京：北京航空航天大学出版社，2006.

[9] 刘万军.Java程序设计实践教程[M]. 北京：清华大学出版社， 2006.

[10] 方贤文.Java语言程序设计[M]. 安徽：安徽科学技术出版社，2014.

[11] 李兴华.java开发实战经典[M]. 北京：清华大学出版社，2009.

第3篇：运筹学最短路径范文

[关键词]卓越计划；运筹学实验；数学建模

[中图分类号]G64 [文献标识码]A [文章编号]1005-6432（2012）41-0145-02

1 引 言

卓越工程师教育培养计划（以下简称“卓越计划”）是为贯彻落实党的十七大提出的走中国特色新型工业化道路、建设创新型国家、建设人力资源强国等战略部署，贯彻落实《国家中长期教育改革和发展规划纲要（2010—2020年）》实施的高等教育重大计划。“卓越计划”具有三个特点：行业企业深度参与培养过程、学校按通用标准和行业标准培养工程人才、强化培养学生的工程能力和创新能力。力求培养一大批面向工业世界、面向世界、面向未来、适应经济社会发展需要的高质量各类型工程技术人才。而高校是实施“卓越计划”的主要阵地，在“卓越计划”的推进过程中加强专业课程改革是十分必要的。

管理运筹学的飞速发展为各个行业把握管理大型组织的复杂性提供了一套十分重要的工具。这些工具集中了世界的各个边缘的知识，其中包括数学、统计与概率论、计量经济学、电机工程甚至生物学。这些外来的技术，如线性规划、排队论、自动控制理论、博弈论、动态规划以及信息论，正在帮助解决各个行业中的实际问题。

因此，在管理运筹学教学中应针对所要解决实际问题的要求和其面临的客观环境条件，作出假设分析，抽象为数学模型，然后应用相关的数学知识加以解决。这就要求问题解决者要知识面广、逻辑思维严密，这对于非数学专业，特别是经管类专业学生实在过于困难，因为，由于受到学时限制，经管类专业学生对高等数学、线性代数、概率与数理统计等先修课程学的比较肤浅，没有或很少经过数学严密的逻辑思维方面的训练，而且经济管理类专业学生是文理科兼收，有相当一部分学生在数学方面的课程普遍底子较差，这客观上就给运筹学教学带来很大困难。因此，为使经济管理类学生能正确全面地掌握各级管理中已被广泛应用，且发展较成熟的最优化理论与方法，并能恰当运用解决实际管理工作中的各种最优化问题，有必要针对经济管理类专业学生的特点和运筹学课程的性质，进行运筹学教学方法的改革。

2 运筹学在数学建模中的应用

管理运筹学在数学建模中有着广泛的应用，多年来许多数学建模竞赛中都涉及运筹学的相关内容。

首先介绍一下图与网络在数学建模中的应用，通过“奥运场馆周边的MS网络设计方案”这个例子来说明其应用。假定奥运会期间每位观众平均出行两次，一次为进出场馆，一次为餐饮，并且出行均采取最短路径。测算题目中20个商区的人流量分布。首先将建模结构图转化为无向赋权图，并鉴于该图的对称性，通过设计一种特殊的流量计算方法对传统的Dijkstra算法进行改进；其次，用MATLAB编写求解最短路的应用程序，可以得到任意两点间的最短路径，进而得到观众出行的最短路径和所经过的商区。

接着通过“彩票发行方案的优化设计模型”这个例子来说明决策论在数学建模中的应用。设计一种“更好”的方案，据此给彩票发行部门提出建议。对此问题，可根据效用理论中存在着主观概率，以及彩票信息在人群中的传播效应，建立主观概率意义下的优化模型。但这个模型是较大规模的非线性规划模型，用穷举法求解比较困难，可采用模拟退火算法来求解，用MATLAB编程实现。

3 结合数学建模改进教学方法

3. 1 更新教学观念，充分重视实验教学

结合数学建模在教学中增加实验教学，以提高学生解决实际问题的能力、培养学生的观察和动手能力为宗旨，有利于培养学生的创新意识与创新能力。在今后的教学中，统筹安排课时，根据教学进度合理安排实验教学时间，力求在完成每一知识点的学习后安排一次实验。实验内容将从实际问题出发，突出本章节的基本原理与基本方法，教师进行监督与指导，有助于学生对理论知识的掌握与理解，同时学生的实践能力得到锻炼，自主学习能力得到提升。

3. 2 分级教学

从学生实际出发，因材施教是将几乎处于同一水平的学生放在一起分别教学的一种教学手段。这种教学体系，根据学生的个体差异，按照不同科目的不同学习能力的高低将学生群体划分成不同的级别或层次，有针对性地进行分班教学。有效的分级教学，能使教师节约精力突出重点积累经验，能让学生尽可能地在各自的最近发展区得到充分的自由发展，谋求各个层次的学生都能获得成功的体验，促进学生的素质得到全面提高。所以说，分级教学是建立在以学生成才为本理念基础上，为实现教学目的的一致性和教学过程的互异性所进行的重要实践，因材施教是分级教学的核心思想。在运筹学教学过程中，也可采用分级教学，培养学生对运筹学的学习兴趣，进而培养数学建模人才。

3. 3 适宜的教学方法

近几年来，由于扩招，生源的扩大，学生基础参差不齐。因此，教师应根据学生具体情况，精心设计教案，调整教学内容、次序和教学组织方式；尽量从学生感兴趣的实例出发，引入正题，以引发学生学习兴趣，吸引学生注意力，使之能更好地掌握理解所学知识，并能恰当运用解决实际问题。

传授新知识时，教师讲授的时间不能过长，内容不能过多，节奏不能过快，并要将基本概念、基本原理在不影响教学效果的情况下，分散介绍，使学生易于接受；否则，教师的讲授将是无效的讲授。运筹学课程内容多、逻辑性强且抽象，需要学生理解掌握。因此，课堂上教师的板书一定要简洁、条理清楚、重点和注意事项突出，并要求学生养成做笔记的良好习惯，以便于课后温习理解和掌握。

3. 4 量体裁衣，突出专业特色

实验教学中实验内容是反映教学目的载体，丰富的实验内容可以激发学生的学习热情和拓宽知识结构。因此，实验内容的选择要“量体裁衣”。面对知识面较广的商学院学生，要想上好运筹学并凸显其实用性，教师需具备充分的定量和经济管理学知识。例如，库存模型通常将需求区分为固定和相对复杂的随机两类，当学生对需求满足特定分布的假设产生疑惑时，教师就应当能够适时介绍需求数据的获取及利用统计学软件对其分布加以判断的方法，这可加深学生对运筹学交叉性的理解。

4 结 论

随着科学技术的进步及“卓越计划”的深入推进，需要对运筹学课程的建设持续探索与实践，不断完善教学方法与教学内容，提高学生的学习兴趣，激发学生的学习热情，真正意义上实现运筹学作为经济管理类专业核心课程应有的重要作用，并锻炼学生的动手能力，培养学生的创新意识与创新能力，以满足创新教育的要求。

参考文献：

[1]教育部. 教育部启动“卓越工程师教育培养计划”[Z].

[2]韩中庚. 数学建模竞赛——获奖论文精选与点评[M].北京：科学出版社，2007（5）.

[3]刘智，汪妍. 管理运筹学教学的思考[J].高师理科学刊，2011（4）：83

第4篇：运筹学最短路径范文

关键词： 最优路径 公交网络 乘客OD量

随着城市建设的迅猛发展，公交出行已成为人们的一个重要出行方式。公共交通作为一个城市经济发展的象征性基础设施，它为广大居民的日常出行提供了方便，因此也关系到一个城市的基本保障问题.优化公交网络，提高公交运载效率越发受到社会的关注，成为人们的迫切需求.

公交规划就是一个多目标的优化问题.进行公交优化设计需要区分主次，设定专门的优化措施.为此，我们提出了“分离目标，逐步解决”的办法.主要是利用数学模型，通过计算机进行处理，得到一个初步优化完善的公交网络.再适当做些调整，使得线路能够分布相对均匀，消除空白的公交区域.

1.Dijkstra算法

Dijkstra算法是很有代表性的最短路算法，其基本思想是，设置顶点集合S并不断地作贪心选择来扩充这个集合.一个顶点属于集合S当且仅当从源到该顶点的最短路径长度已知.初始时，S中仅含有源.设u是G的某一个顶点，把从源到u且中间只经过S中顶点的路称为从源到u的特殊路径，并用数组dist记录当前每个顶点所对应的最短特殊路径长度.Dijkstra算法每次从V-S中取出具有最短特殊路长度的顶点u，将u添加到S中，同时对数组dist作必要的修改.一旦S包含了所有V中顶点，dist就记录了从源到所有其他顶点之间的最短路径长度.

2.公交线路布设模型

2.1公交线路的布设原则

公交网络本身具有快捷、灵活、网络覆盖率高的特点，适合中短距离出行.一般公共汽车的起讫站点相隔在500m到800m之间，如果是在城市中心的话站点之间可以缩短到400m，时间上在客流高峰的时候发车间隔会在3到5分，除此之外的时间可以增加到6到8分，站点设置一般能和其他站点有较好的换乘[1].

2.2城市客流集散点的计算

在已知公交OD矩阵的条件下，将研究区域划分成若干地理性质相似的区域，也可以依据行政意义进行划分，把每一个分好的小区看作一个单一的节点，同时又要能被城市中的主要干路线路贯通，然后通过具体分析可以确定以下指标，并且作为节点的重要度指标.这些指标有地理位置、路况、OD集散程度、人口数量、金融指标等[2].

节点的加权平均值为：L■=■α■·■，L■表示区域内节点i的重要度；

α■表示第j项指标的权重；M是指标数量；e■是节点i的第j项的指标.

e■为区域内所有节点的第j项指标算数平均值.

客流集散强度：E■= ∑■ q■·δ■■，q■是OD点k，1间的OD客流量（人）

δ■■=1，当j，k间的最短路径经过i0，否则

式子中权重值α■的确定即确定出各个标准对于每个节点重要程度的影响效果.

2.3线路起讫点确定

客流量集散地点确定以后，就可以根据公交区域的客流量（OD量），即根据交通区域的发生量还有吸收量最终找到起讫点.

2.3.1按照客流量设定站点

当交通小区处于高峰时期，发生量和吸引量都超过了此线路中间站点的最大运载能力的时候，仅仅依靠中间站点无法完成运载任务，那么这个交通小区就要设置为起讫站点，从而增加运载量.所以可以依据中间站点的运载量设定起讫站.某一个交通小区发生量和运载量超过某一个值时候，需要设定站点.

单个中间站点运输力为C■=60B/t■，C■是中间站点运载力（即人次/高峰小时）；t■是高峰每小时的发车时间间距；B是高峰小时每辆车从中间站搭乘乘客数量的平均值，所取的值可以通过调查得出.交通小区中间站运载力为c（i）=c■N（i），全规划区域的站点个数N■=ρs/d，N■为全规划区域站点的数量；ρ是规划的公交网络的密度；S是规划区域的面积；d为站点的平均间隔.

先根据各个交通小区的出行数量的相对值大小确定出中间站的数量N（i），N（i）=N■T（i）/T，T（i）为交通小区公交乘客发商量或者是吸引量的总和；T为全规划区域的公交发生量的总和.T=■T（i），一个起讫站点的最大运载力为C■=60Rr/（t■k■）.

2.3.2按照实际的要求设置起讫点

一些特殊的地区，如汽车车站、热门旅游景点、船运港湾、生活区等，为了满足乘客的出行路线，服务人民生活，即使总的发生量和吸引量没有达到设站的要求，也可以设定起讫站点.

2.4公交线路的校正和优化

2.4.1设置网络的最佳走向

确定起讫点以后，就要根据路段的不同将行驶所用时间作为阻抗，从而来求得各个起讫站点配对以后的最短路径.又由于这里想到要把优化的网络经过集散点，因此又提出了一个“集散点吸引系数”.

2.4.2直达乘客数量的校正

2.4.2.1公交线路长短的校正

公交网络的路线距离不能过于长和短，必须按照该城市里的实际情况来确定，对已经拟定的待选路线来筛定.对于那些不满足该条件的首末点之间我们不设定公交线路，这时候就要把直达的乘客数量Z■设置为0.

2.4.2.2防止线路间的自相配对

同一个节点是不可以作为相同单向路线起讫站点，因此令Z■=0.

2.4.2.3对于同一区域设定多个站点的校正

当有些划定区域的出行量值非常大的时候，就要确定多个起讫站点了，这个时候，在直达乘客的矩阵里，相对应的起点那一行和终点那一列就要校正，校正次数和这个区域的起讫站点数量是一致的.

2.4.3所设定线路的优化校正

优化线路需要考虑以下问题：校正乘客的OD量，确定OD量的剩余数值，校正行车时间，以及复线系数.

3.实例

我们假设一个交通路线分区和基本路段的路线图，OD量我们假设已经通过调查求出.图中线路上的数字是该条路段车辆的行驶时间（单位：分钟）.

待选路线中的直达乘客数量表示为：

再按照线路的长度要求，防止自相的配对、一个区域设定多个站然后再次对直达的乘客量进行校正.经过最后的计算.OD在[B，C]的乘客量是最大的.这就要设定一个B到C、C到B的公交网，那么最短路径就会是6-12-18-17-16-15-14-20-19.

通过之前的复线系数把第一条公交路通过行车行驶时间修正（其中的数值可以参考待选的最短路径）.到这里，第一条线路设置工作就全部结束了，除去B和C点以外，再一次查询最短路径，逐次去布设第二条、第三条公交线，最后得到完整的网络线路图.

现实生活中公交网络问题受到诸多因素的影响，需要综合考虑这些因素的制约，而且需要搜集大量的数据，并进行实际论证，需要通过数学建模的方法进行研究，合理且便于操作的方法，这也是后续研究的方向.

参考文献：

[1]成邦文，王齐庄，胡绪祖.城市公共交通线网优化设计模型和方法[M].系统工程理论与实践.

[2]李维斌.汽车运输工程[M].北京：人民交通出版社，1987.

[3]赵志峰.城市公共交通线路网规划方法[J].上海交通大学学报，1988，22（6）.

[4]易汉文.城市公交线路系统的规划与设计[M].系统工程，1987，5（1）.

第5篇：运筹学最短路径范文

[关键词]第三方物流 运输决策 运输方式 运输路线

随着社会经济的进一步发展和第三方物流企业的不断壮大，物流利润作为第三利润源泉，已经成为整个供应链的利润“黑洞”。运输决策是第三方物流管理过程中的关键决策问题，进行物流运输决策优化研究，能够提高物流运输管理的科学水平。

一、第三方物流运输优化决策的概念

决策作为物流企业的重要职能，在企业整个发展过程中的作用越来越重要。第三方物流运输优化决策，是第三方物流企业从企业的战略目标出发，运用系统理论和系统工程原理与方法，选择运输方式、载运工具、运输线路，结算运输费用及相关手续费，配备运输人员等，实现运输路径短、运输环节少、运输速度快和费用少地使货物运至目的地。避免不合理的运输和次优化的情况出现。

二、第三方物流运输优化决策的内容

1.第三方物流运输方式的选择决策

（1）第三方物流运输方式选择决策的概念

第三方物流运输方式决策是第三方物流企业根据所运输的原材料、半成品以及产成品的性质、规格、数量等标准，从五种运输方式的特点和适用条件出发，运用决策理论建立数学模型，选择合适的运输方式的过程。第三方物流企业通过对运输方式的决策，选择最适合的运输方式，保证货物安全地、快速地、经济地运到目的地。

（2）第三方物流运输方式选择决策方法

物流运输系统的目标是实现物品安全、快速和低成本的运输，即运输的安全性、速度性、准确性和经济性，这几个因素是相互影响、相互制约的。第三方物流运输方式的选择需要根据第三方物流企业运输环境、运输服务的目标要求，采取以定量分析为主，辅以定性分析的的方法进行选择。单一运输方式的选择就是选择一种运输方式提供运输服务，常用的方法是综合评价法。综合评价法是在确定运输方式评价因素的前提下，根据这些评价因素对运输方式的选择所起的作用不同，分别赋予其相应的权重，然后对几种不同的运输方式进行汇总计算，最终选择一种运输方式的方法。

①评价因素的确定

评价运输方式的因素有运输方式的安全性、速度性、准确性和经济性等。

②权重的确定

企业的环境不同，货物的规格、性质、价格等不同，收货单位要求的运输批量和交货日期也不同，这些特性对运输方式的选择的重要程度也因此不同。所以，可以通过给这些评价因素赋予不同的权数加以区别。设a1、a2、a3、a4分别为安全性、速度性、准确性和经济性的权重。并使其满足：

∑ai=1

但值得注意的是，由于决策者的世界观和价值观有所区别，偏好会有所不同，因而给定的权重不同，这样会影响最终的结果。

③计算运输方式的综合评价值

运输方式的综合评价值的计算公式为

Fi= a1F1i+ a2F2i+ a3F3i+ a4F4i （i=1…5）

A.安全性的数量化。运输方式的安全性可以用某段时间内货物的破损率来表示。破损率越大，则安全性越低； 破损率越小，则安全性越高。假设这五种运输方式的破损率分别为D1、D2、D3、D4和D5，则平均值D为：

D=（D1+ D2+ D3+ D4+ D5）/5

各种运输方式的安全性，可用相对值表示如下：

F1i= Di / D （i=1…5）

B.速度性的数量化。运输方式的速度性主要表现为货物从发货地到收货地所需要的时间，即货物的在途时间。所需时间越短，速度越快；反之，所需时间越长，速度越慢。假设这五种运输方式的所需时间分别为T1、T2、T3、T4和T5，则平均值T为

T=（T1+ T2+ T3+ T4+ T5）/5

各种运输方式的速度性，可用相对值表示如下：

F2i=Ti/T （i=1…5）

C.准确性的数量化。运输方式的准确性主要表现为计划的时间、成本等与实际发生的时间、成本之间的误差，误差率越小，则准确性越高。假设这五种运输方式的误差率分别为Q1、Q2、Q3、Q4和Q5，则平均值Q为：

Q=（Q1+ Q2+ Q3+ Q4+ Q5）/5

各种运输方式的准确性，可用相对值表示如下：

F3i=Qi/Q （i=1…5）

D.经济性的数量化。经济性主要用物流费用的多少来表示，相关物流费用主要包括仓储费、运输费、装卸搬运费、包装费及相关手续费等。在运输过程中支出的总费用越少，则经济性越好。假设这五种运输方式的误差率分别为C1、C2、C3、C4和C5，则平均值C为：

C=（C1+C2+ C3+ C4+ C5）/5

各种运输方式的准确性，可用相对值表示如下：

F4i=Ci/C （i=1…5）

求出综合评价值之后，从定量分析的原则来看，选择数值最大者。

即：max F=max（F1、F2、F3、F4、F5）

多式联运的选择就是选择两种或两种以上的运输方式联合起来提供运输服务。在实际运输中一般铁路与公路联运、公路或铁路与水路联运、航空与公路联运应用较为广泛。

2.载运工具的选择决策

（1）载运工具选择决策的影响因素

尽管现在交通发达可供选择的载运工具较多但对于具体时间、地点条件下的运输不是所有承运人都能很容易地获得所需要的运输工具的。对于运输工具的选择，不仅要考虑运输费用还要考虑仓储因此要综合考虑进行选择。

另外，运输工具的选择还要考虑不同运输方式的营运特性，包括速度可得性、可靠性、能力、频率等。相对来说汽车运输虽费用低，但运量小能力不如火车和轮船而火车、轮船虽运量大费用也比较低但急需时却不如汽车那么容易获得。

（2）载运工具选择决策的方法

运输成本比较决策法，实际上是运载工具决策的量化分析方法。不同的载运工具产生不同的运输成本。因此最佳的运输服务方案是既能满足客户的需要又能使总成本最低。

3.第三方物流运输线路选择决策

（1）概念

第三方物流运输线路的决策是指第三方物流企业从本企业的实际出发，利用运筹学的相关理论和方法对物品从供应地到需求地运输过程中所有的运输线路，选择最优的运输路线的过程。第三方物流运输线路决策可以实现整个运输方案选择和优化的合理化，将货物以最短路线、最快速度和最小费用从供应地运往需求地，快速满足不同顾客的要求，提高客户满意度的同时实现整个供应链的效益最大化。

（2）第三方物流运输线路的选择优化

①起讫点不同的运输线路选择优化

从单一的起点到终点，有很多条线路可以选择，然而，运输线路选择优化的任务就是要找出使总路程的长度最短的线路。这就是运输规划中的最短线路问题，通常称为最短路径法，或者称最短路线方法。即是列出最短运输线路计算表，分步骤地计算。通过比较，选择走近路。

最短路径法可以利用计算机进行求解。把运输网络中的线路（有的称为链）和节点的资料都存入数据库中，选好起点和终点后，计算机可以很快就算出最短路径。

②起讫点相同的运输线路选择优化

起点与终点为同一地点（起迄点重合）的物流运输线路的选择优化，目标是寻求访问各点的次序，以求运行时间或距离最小化。这一类问题没有固定的解题思路，在实践中通常是根据实际情况的不同，结合历史经验寻找比较适合当前情况的方法。历史经验总结如下：应尽量使车辆运行路线形成泪滴状。一般情况下，当运行路线之间不发生交叉式时，车辆运行线路的安排是合理的。

③多个起讫点直达的运输线路选择优化

在有多个供应地向多个收货地供应货物或提供物流服务时，物流运输线路选择优化的任务是要为各收货地指定能够安全、快速、低成本为其服务的供货地，同时要实现整个供货地和收货地系统的最优。

图上作业法包括运输线路不成圈的图上作业法和运输线路成圈的图上作业法。运输线路不成圈的图上作业法较简单。就是从各端点开始，按“各站供需就近调拨”的原则进行调配。成圈的线路流向图要同时达到既无对流现象，又无迂回现象的要求才是最优流向图，所对应的方案为最优运输方案。

三、结论

在我国，现有的第三方物流企业对运输的重视程度各不相同，但通过运输优化决策降低物流成本，为客户提供快速、方便和安全的配送服务的目标是一致的。本文所提供的运输优化决策的内容及方法，应该能为第三方物流企业物流系统的运输决策提供实际操作上的参考。

参考文献：

[1]俞明南，刘申，李阳.物流管理中的运输决策[J].辽宁师范大学学报.2005（1）

[2]胡松评.运输方式选择的决策模型[J]. 物流科技. 2002（02）

第6篇：运筹学最短路径范文

P键词：最短路径；优先权；多初始解；禁忌搜索

中图分类号：F250 文献标识码：A

Abstract： The traditional tabu search algorithm has a strong dependence on the initial solution， and often determines the candidate solution number and the tabu table length according to the experience， which has a great influence on the efficiency of the algorithm. In this paper， TSP problem solving is used to improve the traditional tabu search algorithm by using multiple initial solutions， priority coding， random number of candidate solutions and variable tabu length. At the same time， the convergence rate of the algorithm.

Key words： shortest path； priority； multiple initial solutions； tabu search

在运筹学中，旅行商问题（Traveling Salesman Problem， TSP）是经典的组合优化问题，已被证明具有NP计算复杂性，求解多采用近似算法和启发式算法。禁忌搜索是模仿人类记忆功能的一种方法，通过禁忌表封锁刚搜索过的区域来避免迂回搜索，同时，在特殊情况下，对禁忌区域中的一些优良状态进行特赦，保证搜索的多样性，达到全局最优[1]。传统禁忌搜索算法对初始解具有很强的依赖性，初始解的好坏直接影响着禁忌搜索算法的效率[2]。本文采用多初始解、优先权编码、候选解个数随机化及可变禁忌长度的方法，旨在提升算法效率。

1 禁忌搜索算法的改进

1.1 基于优先权的编码和解码

（1）优先权编码

对于具有n个顶点的网络图，首先对顶点进行编号，确定顶点集合V ，V ，V ，…，V ，再由随机函数产生一个在1～n上服从均匀分布的由n个互不相同的正整数所组成的序列作为顶点优先权PV ，PV ，…，PV ，该优先权序列就构成了本次搜索路径所参照的标准。在后续操作中，只需对换顶点对应的优先权值，便可得到新的优先权序列，确定出新的路径。

（2）解码

本文依据优先权越大越优先的原则确定路径，具体操作如下：

给定一个网络GV，E，其中V=V ，V ，…，V 表示顶点集，E表示边集，假设N V表示所有到达顶点V的点的集合，N V表示所有从顶点V出发的点的集合，从原点s开始，找到N V中优先权最大且不在已知路径结点集合中的结点V 作为搜索结点的下一个结点，令V 为V，继续上述操作，直到V 到达汇点d为止。以此确定新的路径，并求得新路径长度。

1.2 初始解的确定

本文采用多初始解的方式，在算法开始的短期迭代内，对多个初始解进行搜索，并分阶段对当前最优解评价和筛选，最终得到一个相对较优的初始解，具体操作如下：

Step1：假设随机产生了6个初始解，记为X ，i=1，2，…，6，分别进行禁忌搜索，每个解迭代25次，得当前最优解为X ，i=1，2，…，6。转Step2。

Step2：对X ，i=1，2，…，6进行比较和筛选，选出较优的3个解，假设为X ，i=1，3，5，对这3个解分别迭代50次，得当前最优解为X ，i=1，3，5。转Step3。

Step3：对X ，i=1，3，5进行比较和筛选，确定最优解，假设为X ，则以X 为初始解继续迭代。

1.3 候选解的选择

候选解个数对搜索效率影响较大。候选解数量过少，当前最优解更新的几率就很低，会过早的陷入局部最优。候选解数量过多，计算内存和计算时间也跟着增加，不利于算法的快速实现[3]。尤其在顶点数目庞大时，过多的候选解会严重影响运算速度。

传统的禁忌搜索算法将候选解个数确定为一个固定值，很难保证其合理性。为了提升算法效果，在产生候选解时，本文采用以下方式：

（1）在每次迭代时，随机选择d个顶点，放在d个位置上，依次将顶点对应的优先权与后续位置上顶点对应的优先权对换，产生新的路径，并记录对换顶点的下标和新路径的长度，构成候选解集。

（2）为了保证候选解的多样性，在大规模TSP问题中还应做如下规定：假设在第t次迭代时随机选择的顶点集合为A，在第t+1次迭代时随机选择的顶点集合为B，必须保证B中所含A的元素不得超过A所有元素的50%，否则重新选择B中元素。这样可以扩大顶点选择的范围，有效降低相邻迭代中顶点重复选择的概率，提升候选解的多样性。

第7篇：运筹学最短路径范文

【关键词】卷积码；编码；解码

引言

现代通讯技术正以其前所未有的速度发展着，信息传输对于信道的要求越来越高。为了实现通信的可靠性，就需要对于恶劣的信道状况进行控制。增加发送信号功率的做法在实际中经常要受到条件的限制，而采用编程的方法则可以有效的对信道的差错进行控制，因而，在实际中编程控制差错的途径有着广泛的应用。

1、卷积码定义

介绍卷积码之前先谈谈分组码。以串形式进行传输信号时，一般选择分组码。分组码是将k个信息比特编成n个比特，而通常情况下k和n是很小的，这就可以让以串形式传输信号的时候的时延很小。分组码先将信息序列分组，然后再单独对其进行编码。约束长度为N，码元数还是n时，卷积码是与分组码不同的，卷积码编码后的这些码元与好多段的信息都是有联系的，与其联系的段数可以推前至N-1段。所以一共有nN个码元是互相关联的。

2、卷积码与分组码区别和联系

2.1约束关系

卷积码（n，k，m）在编码的时候有一个复杂度，且它的码元与前码元和后码元是成约束关系的。在连续m个码流内，卷积码的距离特性可以用最小距离来表明，并且此码具有纠错的功能。

2.2分组码和卷积码的性能

一般情况下，n和k都是比较小的，卷积码各组间又具有相关性，同时，编码约束长度和利用的译码方式都能够影响卷积码的纠错能力。所以，理论上在码率相同的情况下卷积码的性能是优于分组码的；而实际上，使用中的设备又具有复杂性，实践也证明了分组码的性能是不如卷积码的。

3、编码理论

3.1定义

编码是指为了达到某种目的而对信号进行的一种变换。其逆变换称为译码或解码。编码理论是数学和计算机科学的一个分支，与信息论、概率论、数理统计、随机过程、线性代数、近世代数、数论、有限几何以及组合分析等学科有密切关系。是一种研究信息传输过程中信号编码规律的数学理论。编码能够处理在噪声信道传送资料时的错误倾向。

3.2历史背景

在电报通信中有一种应用很广泛的莫尔斯码，是美国人S.F.B.莫尔斯在1843年设计出来的。据后来证明，这种莫尔斯码与理论上可达到的极限只差百分之十五。而编码理论的形成是在二十世纪三十年代。后来采样定理的提出才为连续信号的离散化奠定基础。1948年C.E.香农提出了信息熵的概念，这又为信源编码奠定了基础。第二年香农又提出了信道容量的概念，这又为信道编码奠定了基础。香农第一定理指出，码字的平均长度只能大于或等于信源的熵。香农第二定理指出只要信息传输速率小于信道容量，就存在一类编码，使信息传输的错误概率可以任意小。1951年，香农指出，在信源的输出有多余的消息时可以通过编码来改变信源的输出，从而信息传输的速率能够与信道容量接近。在今天仍有很广应用的卷积码出现在1955年。在1957年引入了构造简单的循环码数。1959年出现的能够纠正突发错误现象的费尔码和哈格伯尔格码。同年，BCH码得到发表。已用于空间通信的序贯译码提出于1965年。维特比译码和矢量编码法先后提出于1967年和1978年。1980年多进制的BCH码是用数论方法实现的。这种纠错编码技术已在卫星通信中得到了广泛的应用。

4、解（译）码方式

4.1代数译码

代数译码是将卷积码的一个编码约束长度的码段看作是[n0（m+1），k0（m+1）]线性分组码，每次根据（m+1）分支长接收数字，对相应的最早的那个分支上的信息数字进行估计，然后向前推进一个分支。若信息序列＝（10111），相应的码序列c＝（11100001100111）。若接收序列R＝（10100001110111），先根据R的前三个分支（101000）和码树中前三个分支长的所有可能的　8条路径（000000…）、（000011…）、（001110…）、（001101…）、（111011…）、（111000…）、（110101…）和（110110…）进行比较，可知（111001）与接收序列（101000）的距离最小，从而判定第0分支的信息数字为0。然后以R的第1～3分支数字（100001）按同样方法判决，依此类推下去，最后得到信息序列的估值为=（10111），即实现了纠错。译码时采用的接收数字长度为（m+1）n0，所以能纠正的错误长度小于（dmin-1）/2。而在实际应用中采用较多的实现方法还是反馈择多逻辑译码法。

4.2维特比译码过程

维特比译码器有着极其复杂的结构。它的复杂性随着m呈指数增大的形式而越来越复杂。在实际应用中，m的值不会超过10。他在解决数据压缩和码间串扰中有着用途。而它最广泛的用途是在深空通信和卫星上面。

将运筹学中的求最短路径的思维应用到在码的格图上找最小接收序列距离上面，就可以得到一种算法，叫维特比译码。

假设译码器从状态ɑ出发，且每次向右延伸一个分支，对于l＜L，从每个节点出发都有2=2种可能的延伸，其中L是信息序列段数，对l≥L，只有一种可能。接收序列为R=（1010001010110），将此分支与相应的接收数字分支比较，可以得出它们间的距离，再把算出的距离加到被延伸路径的累积距离上。在有不多于两条路径的距离累积值比较后，取距离最小的那一条。当有两条以上取最小值时，可以任取其中的一条。这个最小的一条路径，称为幸存路径。

4.3序贯译码

序贯译码是根据接收序列和编码规则，在整个码树中搜索（既可以前进，也可以后退）出一条与接收序列距离（或其他量度）最小的一种算法。由于它的译码器的复杂性随m值增大而线性增长，在实用中可以选用较大的m值（如20～40）以保证更高的可靠性。许多深空和海事通信系统都采用序贯译码。

5、结论

卷积码是一种纠错编码，纠错编码已经有五十多年的历史，早在1948年，Shannon在他的开创性论文“通信的数学理论”中，第一次阐明了在有扰信道中实现可靠通信的方法，提出了著名的有扰信道编码定理，奠定了纠错码的基石，使纠错码无论在理论上还是在实际中都得到了飞速发展。现代通信中，随着信号序列的传输速率的不断提高，要求卷积码编解码的速度也要不断提高，Viterbi译码由于充分利用信号序列统计概率的特性而具有最佳性能。

参考文献

[1]张宏基等.信源编码[M].北京：人民邮电出版社，1980年：53-56.

第8篇：运筹学最短路径范文

摘要：建立规划项目方法论体系，能帮助规划人员理清规划思路，考虑宏观布局设计、基本战略定位、组织网络架构和营运策略设计等几个不同的方面，目的是达到规划项目有据可查、有理可寻。该体系特色为将数学模型、优化算法、规划方法、指标评价方法等与实际规划项目相结合，从科学与客观条件、人为因素相结合，继而使规划成果更具有合理性及可实施性。

关键词：规划项目方法论优化算法

项目的规划工作一般可以分为五个阶段，依次分别是规划筹备阶段、需求分析阶段、战略定位阶段、规划设计阶段、规划评价阶段。

一、项目规划前期筹备阶段

1.规划筹备阶段是项目规划的起点，主要为规划做好准备工作。该阶段主要包括背景调查和相关资料的收集、整理和初步分析。

背景调查与需求调研是通过与要规划部门网络调研、实地调研（走访、座谈）、电话调研、发放调研表等形式，明确规划的目的和要实现的目标，划定园区用地的边界、确定调研范围和对象、规划的时间、成果形式等。

2、资料初步分析

通过收集背景调查中调研表格和整理访谈笔记等形式，对收集到的地区或行业总量数据（生产总量、消费总量、GDP等）进行整理形成调研报告，对园区的规划定位提出初步建议，确定大略方向。规划筹备阶段形成的主要成果文档内容如下：规划背景（政策背景、基础设施规划背景、产业背景）、规划意义、规划依据、规划原则、规划范围、规划步骤及调研总结（调研阶段、调研方法、调研总结）。国内项目发展现状及规划、某某省项目、相关辐射地区/企业项目。

二、项目规划需求分析阶段

为了深入了解区域项目周边地区的经济发展状况、市场需求、基础设施、服务竞争等情况，必须对项目辐射地区的宏观经济、产业和微观环境情况进行全面调查和研究，根据长远和近期的需求量，确定项目长远和近期的建设规模。主要包括了：（1）需求量预测。用以下三种预测方法分别对货运量进行预测二次多项式回归预测、直线回归预测、灰度预测法等。（2）周边城市现状分析及需求量预测。（3）周边城市处理能力等。

三、项目规划战略定位阶段

在完成详实的定性和定量市场分析和研究之后，规划者必须对项目整体优势、劣势、机会、威胁进行分析(即SWOT分析)，如果某类服务，例如空港、海港、公路货运站场，在整个园区中占有较大比例，还必须进行专项的SWOT分析。这些分析主要作用是帮助园区的高层经营决策者明晰内外部环境，提出发展项目的使命、远景目标和制胜策略，从而进行准确的战略定位，帮助实现其战略目标。这里的制胜策略，是指击败现有及潜在竞争者的计划，包括一系列举措以提高物流服务的水平，项目战略选择的“价值方案”及其实施步骤。这些策略应该严格限制在内部使用。

四、项目规划设计阶段

项目的规划设计阶段就是对项目进行具体的设计，主要包括基础设施平台、信息平台和运营平台三大平台的规划和设计。

1、基础设施平台的规划设计

（1）项目用地规划

园区用地规划主要是对项目建设规模的大小进行确定，园区建设规模太小，会限制区域潜在需求，不利于园区的持续发展。园区规模太大，则可能造成投资浪费和资源闲置的现象。运用专门的统计分析软件（SPSS、EXCEL等）、REA模型等定量分析方法和定性分析方法（SCP模型）相结合，综合考虑实际情况，得出项目现实和潜在的需求量，进一步得出各布局的用地面积。

（2）功能设计

项目的功能设计主要围绕园区的战略定位，采自顶向下的方法，即在确定项目的规划原则以后，对功能规划所涉及的核心功能进行列举和分析，然后通过收集整理一系列国际最先进的项目案例，总结出对要规划项目最适合的经验。随后，整个项目将被划分为几个大功能区域。

（3）布局设计

项目的设施规划与布局设计是指根据项目的战略定位、经营目标和功能设计，在已确认的空间场所内，按照货物的进入、组装、加工等核心流程和主要业务环节，将人员、设备和物料所需要的空间进行最适当的分配和最有效的组合，按照一定的原则和方法设计出合理的技术路线，达到一定的目标（作业流程最短、运输路程最短、费用最小等），以获得最大的经济效益。

对项目中的各建筑设施的选址和规划应采用科学的定量方法，如：运筹学中的一些最优选址方法、最短路径法、最小费用最大流法、有效的物料进出表法、搬运系统分析法、模糊理论中的模糊综合评价法、最优决策方法、SLP-Systematic Layout Planning方法等，项目规划与设施布局的合理性还可以通过建模仿真来进行检验优化。

2、信息平台的规划设计

信息平台规划分为整体规划和详细规划设计。具体规划内容包括：园区整体信息平台的基本概念、广义整体规划定位、设计和狭义整体规划设计。园区详细规划设计包括：项目信息平台的框架结构、层次结构和信息流程设计。

3、运营平台的规划设计

（1）项目的投资开发模式

根据国内外与项目功能相同或相当的基础设施开发建设的经验，在分析我国现有的项目发展模式的基础上，我国经济中心城市项目在发展模式上可能的选择有4种，即经济开发区模式、主体企业引导模式、地产商模式和综合运作模式。

（2）项目的管理模式。项目管理模式的选择应该根据相应的投资开发模式而定。通过上述对项目投资开发模式的分析，其相应的管理模式可以有5种类型，即管理委员会制、股份公司制、业主委员会制、协会制和房东制。

第9篇：运筹学最短路径范文

关键词：物流成本；优化；模型

中图分类号：F713

文献标志码：A 文章编号：1673-291X（2012）17-0144-02

物流成本指产品的空间移动或时间占有中所耗费的各种活劳动和物化劳动的货币表现，是产品在实体流动过程中所支出的人力、物力、财力的总和。作为考证物流在国家经济中价值量化的主要研究指标，物流成本占GDP比重已成为衡量一个国家物流业发展水平的重要指标。2011年，我国社会物流总费用8.4万亿元，与GDP比率为17.8%，与美国等发达国家相比要高出8—10个百分点，社会经济运行的物流成本仍然较高。随着企业内部制造成本管理方法的日渐完善与成熟，通过提高劳动生产率和节约企业内部资源来增加利润空间正逐步减少，改善企业内部物流来增加利润成为当今企业管理的热点和重点，应用物流成本优化模型是控制和降低企业物流成本的一种有效方式[1]。

一、基于财务核算的物流成本优化模型分析

物流成本传统核算方法是在现有会计报表成本资料的基础上，按照一定的原则和方法，从传统成本会计的各项费用中剥离出物流费用。传统法局限于现有会计资料，并且人为因素较多，从而难以准确归集和分配物流成本，因此，需要对物流成本的财务核算进行建模优化。

（一）财务核算优化模型概述

1.任务成本法

任务成本概念是在“物流任务方法”基础上提出的，它改变了传统的物流总成本计算法没有考虑物流系统各环节具体运作过程以及横向的以部门为单位的成本结构，代之以纵向的以功能为单位的成本结构。任务成本方法认为，物流各子系统间相互作用并提供不同水平的客户服务，该方法既能从总成本角度来强调物流系统内各个子系统之间的相关性，又能从系统的角度来提供对不同客户服务的成本信息。但该方法核算过程繁杂，在分配某项作业成本时往往存在人为因素，导致结果不准确，特别是公共作业领域成本分配没有客观标准[2]。

2.作业成本法

作业成本法是以作业或活动为基础，将企业消耗的资源按资源动因分配到作业或活动中，再把收集的作业成本按作业动因分配到成本对象中的核算方法，其基本逻辑是：各种资源耗费驱动成本的发生，使各种产品成本多少应取决于对各种活动的消耗量，并以此来核算成本具有更大的准确性。作业成本法是应用最为广泛的物流成本财务核算优化模型。

作业成本法不仅可以更全面的核算物流成本，也为企业考核物流项作业活动成本提供绩效考评的依据。它可以分析针对每一种（类）产品在物流各个作业环节上的花费，寻找成本挖潜对象和目标；可以对未来物流成本进行预测，制定针对性的成本控制计划和长期的物流成本战略，及时掌控成本变化信息，利于形成动态的成本管控体系。

3.M—A模型法（Mission Cost—ABC）

任务成本法和作业成本法的逻辑思路是一致的，都是以过程为导向，用成本来追溯特定的活动或任务成本。M—A模型法将任务成本法与作业成本法结合在一起进行物流成本核算，构建物流成本核算的M—A模型，界定了物流成本的涵盖范围，明确了物流成本数据的信息来源，描述了M—A模型的理论框架。该方法把物流成本的测算过程分为两个阶段：根据任务成本法确定成本目标，再由作业成本法分析物流活动及相关资源，并对企业物流活动中各个成本要素向各个环节的分配途径作了清晰、直观的描述。

（二）财务核算优化模型比较分析

上述三种物流成本核算的优化模型各有利弊，在实际运用中要根据企业具体情况进行选择。三种模型的优缺点和适用范围见表1。

二、基于成本控制的物流成本优化模型分析

物流成本控制建模具有很强的实用性与针对性，可以对管理方面提供依据，可以用于企业高层分析财务信息以制定相应的物流政策。成本控制建模多用运筹学的方法，主要有排队网络法、极大代数法、Petri网法等形式化建模技术以及活动循环图、流程图、面向对象的建模技术等非形式化建模技术。

（一）成本控制优化模型概述

从具有可操作性的物流成本控制模型研究来分析，可将现有的成本控制优化模型分为两大类，分别是针对具体物流作业的和全局式规划的优化模型。

1.针对具体物流作业的成本优化模型

首先是库存问题。现有研究中，主要是对各种库存模型讨论，大多集中在生产/库存系统和库存/分配系统。经济批量（EOQ）模型是最早应用较为广泛的库存模型理论，此后很多学者从不同角度出发，应用不同理论方法对库存管理进行了广泛研究，并提出了一系列经典模型，例如，经济生产批量模型、允许缺货的经济订购批量模型、经济订购批量折扣模型、需求为随机变量的订货模型、物料需求计划和准时化生产方法等等[3]。

其次是运输及配送中的物流成本优化模型。在企业物流层面，对运输成本的研究通常与采购、库存和网点建设等活动相联系。即运输成本体现出某种一体化特性，目前物流运输成本优化模型则多是利用线性和非线性的运筹学理论，如最短路径法、最小费用流法等进行建模计算，以实现运输总成本最小。

2．全局化物流成本优化模型

第一类是供应商选择物流成本模型。关于供应商选择的物流成本模型涉及面较广，混合型整数非线性规划模型，将实际价格、库存、运输成本纳入物流总成本的考虑范围，此外，采购预算限制、质量、服务等因素也被包括到该模型之中[4]。

第二类是物流网络／布局策略中的物流成本。国外学者对物流布局／区位问题的研究，最早开始于货物运输网络设计和设施选址领域，以后加入了整体网络规划。其中，公共物流终端模型利用排队理论和非线性规划开发了用于确定最优规模和最佳布局的数学模型。该模型考虑了运输成本和设施成本之间的交替作用，以实现成本最小化；该模型在日本得到实际运用。最近的研究是应用博弈论讨论区域物流网络。

第三类是逆向物流成本优化模型。因为逆向物流几乎包括了所有的物流活动，所以对其的研究包括了配送规划、库存控制、生产规划等领域。1992年，Pohlen和Farris就提出可以利用个别渠道成员的既有功能与能力执行回收和再制造任务[5]。

（二）成本控制模型比较分析

根据上述物流成本控制优化模型的介绍和使用情况，从两方面分析其优缺点并据此划分适用范围，如表2所示。

三、物流成本优化模型分析小结

财务核算优化模型的产生很大程度解决了原有会计制度对物流成本核算的片面性，帮助企业更加全面完整的了解内部物流成本的总额和分布情况，为物流成本控制提供了基础。基于财务核算的成本优化模型开始是针对作业环节进行建模优化以核算物流作业成本，后来发展到从产品甚至供应链的角度进行成本核算。成本控制优化模型则是在较为全面的物流成本会计资料的基础上运用运筹、数理分析等方法对物流流程包括库存、运输等物流项目进行优化，以达到最优物流成本。基于成本控制的优化模型是从开始优化某一具体环节到将整个物流流程都纳入模型中以求得整体最优解。

在实际操作中虽然能取得整体最优是企业运营的最理想状态，但是并不代表所有企业都应选择最全面先进的优化模型。

首先，有些企业虽然没有建立专门的物流成本会计科目，但是因为企业费用发生明确具体，可以很容易地进行归集和分配，并不需要再去建模优化核算流程。有些企业的物流流程较为简单，并不包括所有物流活动，或者产品服务较为单一，使用有针对性的优化模型其实也可以达到很好的效果。如专门进行仓储或者运输的企业只要根据企业情况有针对性，建模，就完全可以达到减少物流成本的目的。

其次，在企业构建一个从核算到成本控制的整体物流优化模型，需要专门的技术软件和设备，这是一笔不小的开支，并不是所有企业都能承担。而且整体最优模型考虑因素庞杂繁多，当企业在使用时需要添加海量的变量和限制条件，只要有一个参数设置错误结果都会与最优解相距甚远，而且每当企业环境有变化都需要从新调整模型，这需要使用此类模型的企业有雄厚的技术、资金支持，在企业内要设有专门的技术部门，这也增加了企业管理开支。

最后，只有不同部门间合作协调，信息畅通的企业才能发挥整体优化模型的最佳效果。如果企业部门信息不能及时反馈到优化模型，那么得出的最优解结果也没有实际操作的意义。所以，要构建整体优化模型的企业首先要对企业流程进行优化重组。

综上，物流成本优化模型的选择最重要的是要符合企业现实情况，而不是一味选择最先进，最全面的模型。本文通过对物流成本优化模型的介绍分析，使企业可以对各个模型的适用范围有所了解，便于企业选择最为合适的优化模型。

参考文献：

[1] 2011年中国社会物流统计数据xxw3441.blog.省略/blog/static/75383624201211791620468/

[2] 何伟.生产企业物流成本控制[J].铁路采购与物流，2010，（11）.

[3] 耿邯利.企业成本会计核算优化[J]．现代商业，2008，（6）.

[4] 张人千，魏法杰，等.基于成本的车间作业优化模型及实证研究[J].中国管理科学，2002，（5）.

[5] 黄湘民，刘大成，周阳方.国外物流成本研究前沿及进展[J].商业研究，2008，（23）.[责任编辑　王　佳]

收稿日期：2012-04-13