用遗传算法解决车辆优化调度问题
以下是资料介绍,如需要完整的请充值下载.
1.无需注册登录,支付后按照提示操作即可获取该资料.
2.资料以网页介绍的为准,下载后不会有水印.资料仅供学习参考之用.
密 惠 保
1.无需注册登录,支付后按照提示操作即可获取该资料.
2.资料以网页介绍的为准,下载后不会有水印.资料仅供学习参考之用.
密 惠 保
资料介绍：
物流配送车辆优化调度的研究动态和水平
1.2.1 问题的提出
物流配送车辆优化调度问题最早是由Dantzig和Ramser于1959年首次提出，自此，很快引起运筹学、应用数学、组合数学、图论与网络分析、物流科学、计算机应用等学科的专家与运输计划制定者和管理者的极大重视，成为运筹学与组合优化领域的前沿与研究热点问题。各学科专家对该问题进行了大量的理论研究及实验分析，取得了很大的进展。
国外对物流配送车辆优化调度问题作了大量而深入的研究，例如早在1983年Bodin, Golden等人在他们的综述文章中就列举了700余篇文献。在Christofides(1985)，Golden和Assad(1988)编辑的论文集，以及Altinkermer和Gavish(1991)，Laporte(1992)，Salhi(1993)等的综述文章中都进行了详尽阐述。该领域的代表人物有Bodin，Christfids，Golden，Assad，Ball，Laporte，Rinnooy Kan，Lenstra，Desrosiers和Desrochers等人［１］［３］。
国内对物流配送车辆优化调度问题的研究相当少，主要研究对象是旅行商问题(Traveling Salesman Problem，简称TSP)、中国邮递员问题(Chinese Postman Problem ,简称CPP)、有向中国邮递员问题(Directed Chinese Postman Problem，简称DCPP)等，系统性研究还尚未见到。李大为等(1998)以TSP的最近距离启发式为基础，通过设置评价函数来处理时间窗约束，求解了简单的VSP。张震(1995)针对单车场满载问题，提出了考虑运输行程约束的优化方法。遗传算法和神经网络方法对简单TSP的求解取得了一定成果。蔡延光等(1998)应用并行表搜索法和模拟退火法针对简单情形对满载问题进行了求解［３］［５］。 think58好，好think58 [资料来源：www.THINK58.com]
目前，问题的形式己有很大发展，该问题以不仅仅局限于汽车运输领域，在水运、航空、通讯、电力、工业管理、计算机应用等领域也有一定的应用，其算法己用于航空乘务员轮班安排、轮船公司运送货物经过港口与货物安排的优化设计、交通车线路安排、生产系统中的计划与控制等多种组合优化问题。
1.2.2 分类
VSP被提出后，Linus (1981),Bodin和Golden(1981) , Bodin(1983) , Assad(1988) ,Desrochers, Lenstra和Savelsbergh(1990)等许多学者对VSP从不同角度，按不同的标准进行了分类。
按任务特征分，有纯装问题或纯卸题(pure pick up or pure delivery, 车辆在所有任务点装货或卸货，及集货或送货问题) 及装卸混合问题(combined pick up and delivery，每项任务有不同的装货点和卸货点，即集货、送货一体化问题)。
按任务性质分，有对弧服务问题(如中国邮递员问题)和对点服务问题(如旅行商问题)以及混合服务问题(如交通车线路安排问题)。
按车辆载货状况分，有满载问题(货运量不小于车辆容量，完成一项任务需要不只一辆车)和非满载问题(货运量小于车辆容量，多项任务用一辆车)。
按车场(或货场、配送中心等)数目分，有单车场问题和多车场问题。
按车辆类型数分，有单车型问题(所有车辆容量相同)和多车型问题(执行任务的车辆容量不完全相同)。
按车辆对车场的所属关系分，有车辆开放问题(车辆可以不返回其发出车场)和车辆封闭问题(车辆必须返回其发出车场)。
按优化目标数来分，有单目标问题和多目标问题。
由于情况的不同，车辆优化调度问题的模型构造及算法有很大的差别。
1.2.3 基本问题与基本方法
为简化货运车辆优化调度问题的求解，常常应用一些技术将问题分解或转化成一个或几个已经研究过的基本问题，再用相应比较成熟的基本理论和方法，以得到原货运车辆优化调度问题的最优解或满意解。
常用的基本问题有：旅行商问题、分派问题、运输问题、背包问题最短路问题、最小费用流问题、中国邮路问题等。
常用的基本理论和方法有：分枝界定法、割平面法、线性规划法、动态规划法、匹配理论、对偶理论、组合理论、线搜索技术、列生成技术、概率分析、统计分析、最差情况分析、经验分析等。
1.2.4 算法
货运车辆优化调度问题的求解方法非常丰富，目前主要有以下四类：
1、系统仿真法(Simulation )
此方法最早由Golden和Skiscim于1986年提出，主要应用于行车线路与物流中心区位的选择，优点在于可直接观察系统安排的效率与效果，但由于问题的实际情况多变且具有不确定性，是否能将实际的配送情形系统逻辑化为仿真程序，往往令人质疑。 本文来自think58 [来源：http://www.think58.com]
2、人机互动法
此方法结合人类决策与计算机计算能力，在求解的过程中，通过高度的人机交互模式，结合专家的决策信息，并据以计算出结果；优点是寻优的过程中，决策者可以很清楚地看到各约束条件之间的替代关系，以及参数变化可能导致的成本变化。
3、精确解法(Exact procedures )
精确解法指可求出最优解的算法，精确解法主要有：分枝界定法(Branch and Bound Approach)、割平面法(Cutting Planes Approach)、网络流算法(Network Flow Approach)、动态规划方法(Dynamic Programming Approach)。精确算法的计算量一般随着问题规模的增大呈指数增长。
4、启发式解法(Heuristics)
由于上述三种方法的求解效率较差，所以大部分的学者都致力于启发式解法的发展。该方法在解题时可减少搜寻的次数，所以是一种容易且快速的求解困难问题的算法。目前已提出的启发式算法很多，按Cesar Rego的分类法有以下四类：
（1）算法(Constructive Algorithm)
根据一些准则，每一次将一个不在线路上的点增加进线路，直到所有的点都被安排进线路为止。该类算法的每一步，把当前的线路构形（很可能是不可行的）跟另外的构形（也可能是不可行的）进行比较并加以改进，后者是根据某个判别函数（例如总费用）会产生最大限度的节约的构形，或是以最小代价把一个在当前构形上的需求对象插入进来的构形(Clarke和Wright，1964；Mole和Jamesson，1976；Paessens，1988；Altinkemer和Gavish，1991；Desrochers和Verhoog，1989)。 本文来自think58
构造算法是最早提出用来解决旅行商问题(Traveling Salesman Problem,简称TSP)及VSP的，这些方法一般速度快，也很灵活，但这类方法有时找到的解离最优解差的很远。
（2）阶段法(Two-phase Algorithm)
两阶段法是：第一阶段得到一可行解，第二阶段通过对点的调整，在始终保持解可行的情况下，力图向最优目标靠近，每一步都产生另一个可行解以代替原来的解，使目标函数值得以改进，一直继续到不能再改进目标函数值为止(Gillett和Miller，1974；Christofids、Mingozzi和Toth，1979；Fisher和Jaikumar，1981；Renaud、Boctor和Laporte，1996；Bramel和Simchi-Levi，1995)。一般第一阶段常用构造算法，在第二阶段常用的改进技术有2-opt(Lin，1965)、3-opt(Lin Kernighan，1973)和Or-opt(Or，1976)交换法，这是一种在解的邻域中搜索，对初始解进行某种程度优化的算法，以改进初始解。
在两阶段法求解过程中，常常采用交互式优化技术，把人的主观能动作用结合到问题的求解过程中，其主要思想是：有经验的决策者具有对结果和参数的某种判断能力，并且根据知识直感，把主观的估计加到优化模型中去。这样做通常会增加模型最终实现并被采用的可能性。
（3）不完全优化算法(Incomplete Optimization Algorithm) [来源：http://www.think58.com]
以启发式准则来代替精确算法中的决策准则，以缩小解搜索的空间(Toth、 Christofides和Mingozzi，1979等)。
（4）改进算法(Improvement Algorithm)
从一个初始解开始，通过对当前的解进行反复地局部扰乱(Perturbations)以达到较好的解。基于启发式的并行算法和一些称为亚启发式算法(Metaheuristics、Laporte 和Osman，1996)的方法都属于此类(Cesar Rego，1998；Gendrea、Laporte和Potvin，1994)［８］。
亚启发式算法包括表搜索算法(Table Search)、模拟退火算法(Simulated Annealing)、遗传算法(Genetic Algorithm)和神经网络(Neural Networks)方法。
1.2.1 问题的提出
物流配送车辆优化调度问题最早是由Dantzig和Ramser于1959年首次提出，自此，很快引起运筹学、应用数学、组合数学、图论与网络分析、物流科学、计算机应用等学科的专家与运输计划制定者和管理者的极大重视，成为运筹学与组合优化领域的前沿与研究热点问题。各学科专家对该问题进行了大量的理论研究及实验分析，取得了很大的进展。
国外对物流配送车辆优化调度问题作了大量而深入的研究，例如早在1983年Bodin, Golden等人在他们的综述文章中就列举了700余篇文献。在Christofides(1985)，Golden和Assad(1988)编辑的论文集，以及Altinkermer和Gavish(1991)，Laporte(1992)，Salhi(1993)等的综述文章中都进行了详尽阐述。该领域的代表人物有Bodin，Christfids，Golden，Assad，Ball，Laporte，Rinnooy Kan，Lenstra，Desrosiers和Desrochers等人［１］［３］。
国内对物流配送车辆优化调度问题的研究相当少，主要研究对象是旅行商问题(Traveling Salesman Problem，简称TSP)、中国邮递员问题(Chinese Postman Problem ,简称CPP)、有向中国邮递员问题(Directed Chinese Postman Problem，简称DCPP)等，系统性研究还尚未见到。李大为等(1998)以TSP的最近距离启发式为基础，通过设置评价函数来处理时间窗约束，求解了简单的VSP。张震(1995)针对单车场满载问题，提出了考虑运输行程约束的优化方法。遗传算法和神经网络方法对简单TSP的求解取得了一定成果。蔡延光等(1998)应用并行表搜索法和模拟退火法针对简单情形对满载问题进行了求解［３］［５］。 think58好，好think58 [资料来源：www.THINK58.com]
目前，问题的形式己有很大发展，该问题以不仅仅局限于汽车运输领域，在水运、航空、通讯、电力、工业管理、计算机应用等领域也有一定的应用，其算法己用于航空乘务员轮班安排、轮船公司运送货物经过港口与货物安排的优化设计、交通车线路安排、生产系统中的计划与控制等多种组合优化问题。
1.2.2 分类
VSP被提出后，Linus (1981),Bodin和Golden(1981) , Bodin(1983) , Assad(1988) ,Desrochers, Lenstra和Savelsbergh(1990)等许多学者对VSP从不同角度，按不同的标准进行了分类。
按任务特征分，有纯装问题或纯卸题(pure pick up or pure delivery, 车辆在所有任务点装货或卸货，及集货或送货问题) 及装卸混合问题(combined pick up and delivery，每项任务有不同的装货点和卸货点，即集货、送货一体化问题)。
按任务性质分，有对弧服务问题(如中国邮递员问题)和对点服务问题(如旅行商问题)以及混合服务问题(如交通车线路安排问题)。
按车辆载货状况分，有满载问题(货运量不小于车辆容量，完成一项任务需要不只一辆车)和非满载问题(货运量小于车辆容量，多项任务用一辆车)。
按车场(或货场、配送中心等)数目分，有单车场问题和多车场问题。
按车辆类型数分，有单车型问题(所有车辆容量相同)和多车型问题(执行任务的车辆容量不完全相同)。
本文来自think58
[资料来源：www.THINK58.com]
按车辆对车场的所属关系分，有车辆开放问题(车辆可以不返回其发出车场)和车辆封闭问题(车辆必须返回其发出车场)。
按优化目标数来分，有单目标问题和多目标问题。
由于情况的不同，车辆优化调度问题的模型构造及算法有很大的差别。
1.2.3 基本问题与基本方法
为简化货运车辆优化调度问题的求解，常常应用一些技术将问题分解或转化成一个或几个已经研究过的基本问题，再用相应比较成熟的基本理论和方法，以得到原货运车辆优化调度问题的最优解或满意解。
常用的基本问题有：旅行商问题、分派问题、运输问题、背包问题最短路问题、最小费用流问题、中国邮路问题等。
常用的基本理论和方法有：分枝界定法、割平面法、线性规划法、动态规划法、匹配理论、对偶理论、组合理论、线搜索技术、列生成技术、概率分析、统计分析、最差情况分析、经验分析等。
1.2.4 算法
货运车辆优化调度问题的求解方法非常丰富，目前主要有以下四类：
1、系统仿真法(Simulation )
此方法最早由Golden和Skiscim于1986年提出，主要应用于行车线路与物流中心区位的选择，优点在于可直接观察系统安排的效率与效果，但由于问题的实际情况多变且具有不确定性，是否能将实际的配送情形系统逻辑化为仿真程序，往往令人质疑。 本文来自think58 [来源：http://www.think58.com]
2、人机互动法
此方法结合人类决策与计算机计算能力，在求解的过程中，通过高度的人机交互模式，结合专家的决策信息，并据以计算出结果；优点是寻优的过程中，决策者可以很清楚地看到各约束条件之间的替代关系，以及参数变化可能导致的成本变化。
3、精确解法(Exact procedures )
精确解法指可求出最优解的算法，精确解法主要有：分枝界定法(Branch and Bound Approach)、割平面法(Cutting Planes Approach)、网络流算法(Network Flow Approach)、动态规划方法(Dynamic Programming Approach)。精确算法的计算量一般随着问题规模的增大呈指数增长。
4、启发式解法(Heuristics)
由于上述三种方法的求解效率较差，所以大部分的学者都致力于启发式解法的发展。该方法在解题时可减少搜寻的次数，所以是一种容易且快速的求解困难问题的算法。目前已提出的启发式算法很多，按Cesar Rego的分类法有以下四类：
（1）算法(Constructive Algorithm)
根据一些准则，每一次将一个不在线路上的点增加进线路，直到所有的点都被安排进线路为止。该类算法的每一步，把当前的线路构形（很可能是不可行的）跟另外的构形（也可能是不可行的）进行比较并加以改进，后者是根据某个判别函数（例如总费用）会产生最大限度的节约的构形，或是以最小代价把一个在当前构形上的需求对象插入进来的构形(Clarke和Wright，1964；Mole和Jamesson，1976；Paessens，1988；Altinkemer和Gavish，1991；Desrochers和Verhoog，1989)。 本文来自think58
[资料来源：http://THINK58.com]
构造算法是最早提出用来解决旅行商问题(Traveling Salesman Problem,简称TSP)及VSP的，这些方法一般速度快，也很灵活，但这类方法有时找到的解离最优解差的很远。
（2）阶段法(Two-phase Algorithm)
两阶段法是：第一阶段得到一可行解，第二阶段通过对点的调整，在始终保持解可行的情况下，力图向最优目标靠近，每一步都产生另一个可行解以代替原来的解，使目标函数值得以改进，一直继续到不能再改进目标函数值为止(Gillett和Miller，1974；Christofids、Mingozzi和Toth，1979；Fisher和Jaikumar，1981；Renaud、Boctor和Laporte，1996；Bramel和Simchi-Levi，1995)。一般第一阶段常用构造算法，在第二阶段常用的改进技术有2-opt(Lin，1965)、3-opt(Lin Kernighan，1973)和Or-opt(Or，1976)交换法，这是一种在解的邻域中搜索，对初始解进行某种程度优化的算法，以改进初始解。
在两阶段法求解过程中，常常采用交互式优化技术，把人的主观能动作用结合到问题的求解过程中，其主要思想是：有经验的决策者具有对结果和参数的某种判断能力，并且根据知识直感，把主观的估计加到优化模型中去。这样做通常会增加模型最终实现并被采用的可能性。
（3）不完全优化算法(Incomplete Optimization Algorithm) [来源：http://www.think58.com]
以启发式准则来代替精确算法中的决策准则，以缩小解搜索的空间(Toth、 Christofides和Mingozzi，1979等)。
（4）改进算法(Improvement Algorithm)
从一个初始解开始，通过对当前的解进行反复地局部扰乱(Perturbations)以达到较好的解。基于启发式的并行算法和一些称为亚启发式算法(Metaheuristics、Laporte 和Osman，1996)的方法都属于此类(Cesar Rego，1998；Gendrea、Laporte和Potvin，1994)［８］。
亚启发式算法包括表搜索算法(Table Search)、模拟退火算法(Simulated Annealing)、遗传算法(Genetic Algorithm)和神经网络(Neural Networks)方法。