基于聚类的改进蚁群算法对vrptw问题的应用研究

《基于聚类的改进蚁群算法对vrptw问题的应用研究》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、国外将物流配送车辆优化调度问题归结为VRP问题和VSP问题（VehicleSchedulingProblem）。VRP问题首次于1959年被Dantzig和Ramser提出，并很快引起运筹学、组合数学、应用数学、网络分析与图论、计算机应用、物流科学等学科的专家以及配送计划的制定者和管理者的极大的重视，从而成为运筹学与组合优化领域的前沿与研究热点。近年来，许多学者都利用蚁群算法对各种VRP问题进行了大量的研究，并设计了各种类型的蚁群算法，由此形成了一些可行的解决方案。物流配送车辆优化调度，是物流配送优化中关键的一环。随着物流配送向集约化、一体化的方向发展，常对配送的各环节进行综合考虑，主要是配

2、送车辆的集货、配货及送货过程[5]。VRP问题根据不同的标准可分为不同的类别。根据物流配送中心的数目，可分为单物流配送中心问题(配送系统中仅有一个物流中心）和多物流配送中心问题（配送系统中存在多个物流中心）；根据运输车辆的种类多少，分为单车型问题（配送车辆的载重量完全相同）和多车型问题（所有配送车辆的载重量不完全相同）；根据车辆对车场的所属关系分，有车辆开放问题（车辆在完成配送任务后可以不返回其发出的车场）和车辆封闭问题（即车辆在完成配送任务后必须返回其发出的车场）；根据车辆是否有容量约束分，有容量约束的VRP问题和无容量约束的VRP问题（即TSP问题）；根据货运任务的性质分，有纯送货问题（

3、仅考虑从物流配送中心向用户送货，也称为纯卸问题）或纯取货问题（仅考虑把各用户供应的货物取到物流中心，也称为纯装问题）以及取送混合问题（既考虑将用户需求的货物从物流配送中心送达到各个用户，同时也考虑将各用户供应的货物从用户取到物流配送中心，也称为装卸混合问题或集货、送货一体化问题）；根据优化的目标数分，有单目标问题（仅考虑一个目标约束）和多目标问题（同时考虑多个目标约束）；根据货运任务的完成是否有时间约束，又可分为有时间窗约束的VRP问题（VRPTW）和无时间窗约束的VRP问题；根据货运任务时间窗约束的强度，又可将VRPTW问题划分为硬时间窗约束的VRP问题（VRPHTW，VehicleRou

4、tingProblemwithHardTimeWindows，用户要求货物必须在规定的时间窗内送达或取走，但是不能提前也不能拖后）和软时间窗约束的VRP问题-3-（VRPSTW，VehicleRoutingProblemwithSoftTimeWindows，用户要求将货物尽量在规定的时间窗内送达或取走，可以提前或拖后，但在提前或拖后时，要对配送企业实施一定的惩罚）。VRPTW是在针对用户对货物需求量、要求的被服务时间等约束条件下，规划使车辆行驶的总成本（路程或时间）最优化，所以深入研究VRPTW问题将对企业有效制定车辆调度方案具有更加现实的意义。1.3国内外发展现状近几十年来，国外对物流配

5、送车辆路径规划问题作了大量而深入的研究，Eilon等人在1971年提出了将动态规划法用于固定车辆数的VRP，并通过递归方法对其进行求解。其后，状态空间松弛变量被Christofields提出，减少了状态数量。1974年，Gillett,Wren等人提出Sweep算法（扫描法）。Christofides等人在1981年提出了k度中心树和相关的算法，主要对固定车辆数m的m-TSP进行k度中心树松弛。Bodin，Golden[6]等人在1983年的综述文章中就列举了几百余篇VRP相关的文献；Christofides[7]，Golden，Assadt[8]，Altinkerner，Gavish，La

6、porte[9]和Salhi[10]等在他们的论述文章中对VRP问题都进行了详尽的阐述。1991年，Gendreau等人将禁忌搜索方法应用于VRP。J.tzwrence在1996年将遗传算法用于求解VRP的问题，并有效求解出带时间窗口的VRP问题。Barnier将大范围、粗粒度的遗传算法与约束满足问题（CSP）的技术相结合，通过遗传算法这一寻优算法对CSP参数的子域（基因的适应度通过CSP解的计算而得到）进行处理，从而减小搜索的空间，降低CSP问题的目标函数和遗传算法的复杂度[11]。在国内，20世纪90年代后才逐渐兴起了对有关车辆调度问题的研究，比国外相对落后。李大卫[12]等（1988）

7、以TSP的最近距离启发式为研究基础，通过设置评价函数来处理时间窗的约束问题，求解了简单的VSP。张震（1995）针对单车场满载问题，提出了考虑运输行程约束的优化方法。蔡延光[13]等（1998）应用并行表搜索算法和模拟退火算法对满载问题进行了求解，但只针对简单情形。1999年，张涛等人用3-OPT算法加强局部搜索能力，通过遗传算法保证搜索的全局性，得到了针对VRP的混合算法。1999年，姜大立等人在分析VRP