物流配送车辆调度问题的模型和算法研究

《物流配送车辆调度问题的模型和算法研究》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、北方交通大学博士学位论文物流配送车辆调度问题的模型和算法研究姓名：郎茂祥申请学位级别：博士专业：交通运输规划与管理指导教师：胡思继2002.2.1北方交通大学博士学位论文摘要摘要随着市场经济的发展和物流专业化水平的提高，物流配送业得到了迅速发展。在物流配送业务中，配送车辆调度问题的涉及面较广，需要考虑的因素较多，对企业提高服务质量、降低物流成本、增加经济效益的影响也较大。在现实生产和生活中，邮政投递问题、公共汽车调度问题、电力调度问题、管道铺设问题、计算机网络拓扑设计问题等都可以抽象为物流配送车辆调度

2、问题。因此，本文将物流配送车辆调度问题作为研究对象，具有一定的理论和现实意义。物流配送车辆调度问题作为一个NP难题，随着客户数量的增加，可选的配送路径方案数量将以指数速度急剧增长。因此，用启发式算法求解该问题就成为人们研究的一个重要方向。本文将在建立物流配送车辆调度问题的数学模型的基础上，研究用爬山算法、禁忌搜索算法、模拟退火算法、遗传算法等现代优化计算方法对其求解。／本文围绕物流配送车辆调度问题的模型和算法开展研究，主要做了以下工L作：(1)在对物流配送车辆调度问题的结构要素进行系统分析的基础上，建

3、立了无时限单向物流配送车辆调度问题的基于直观描述的数学模型。该模型考虑了较为接近实际的约束条件，设计了多个目标函数，并具有简单、直观、易于理解、易于设计算法求解及可扩充性强等特点。(2)为构造物流配送车辆调度问题的求解算法研究提出了两种新的解的表示方法和两种新的邻域搜索策略。论文还分别针对物流配送车辆调度问题的多种解的表示方法设计了相应的解的评价方法和具体的邻域选点策略，从而为构造该问题的爬山算法、禁忌搜索算法、模拟退火算法及遗传算法奠定了基础。(3)设计并实现了无时限单向物流配送车辆调度问题的爬山算

4、法，并通过实验计算研究了解的表示方法、邻域选点策略、搜索次数等算法策略和运行参数对该算法性能的影响。(4)设计并实现了无时限单向物流配送车辆调度问题的禁忌搜索算法，并通过实验计算研究了禁忌长度、邻域选点策略、迭代搜索策略等算法策略和运行参数对该算法性能的影响。(5)设计并实现了无时限单向物流配送车辆调度问题的模拟退火算法，并通过实验计算研究了初始温度、降温速度、迭代搜索策略等算法策略和运行参数对该算法性能的影响。(6)设计并实现了无时限单向物流配送车辆调度问题的遗传算法，并通过实验计算研究了个体编码方

5、法、选择策略、交叉算子、变异算子等算法策略以及交叉概率、变异概率、群体规模、进化代数等运行参数对该算法性能的影响。北方交通大学博士学位论文摘要(7)在分析基本遗传算法的不足的基础上，提出将局部搜索能力较强的爬山算法和模拟退火算法与基本遗传算法结合，从而构造了无时限单向物流配送车辆调度问题的爬山遗传算法和模拟退火遗传算法，进而通过实验计算研究了这两种混合遗传算法的性能。(8)分别建立了硬时间窗和软时间窗单向物流配送车辆调度问题的基于直观描述的数学模型，在此基础上设计和实现了求解这两类问题的禁忌搜索算法和

6、模拟退火算法，进而通过实验计算研究了上述算法的性能。(9)研究提出了更具一般性的双向物流配送车辆调度问题，在此基础上分别建立了无时限、硬时间窗和软时间窗双向物流配送车辆调度问题的基于直观描述的数学模型，并设计和实现了求解上述三类问题的禁忌搜索算法和模拟退火算法，进而通过实验计算研究了上述算法的性能。针对硬时间窗和软时间窗双向物流配送车辆调度问题中因每个客户有供应和需求两个时间窗从而造成求解困难的情况，论文提出了一种通过拆分客户的方法将双时间窗问题转化为单时间窗问题进行求解的思路。(10)在求解无时限、

7、硬时间窗和软时间窗双向物流配送车辆调度问题时，对双向配送策略的计算结果与单向配送策略的计算结果进行了比较，从而说明了采用双向配送策略求解双向物流配送车辆调度问题对于配送企业节省配送车辆、减少配送里程，从而降低配送成本、提高经济效益的重要意义。)2，k一关键词：物流配送；车辆调度退火算法：遗传算法)————。—一II算法；堕煞北方交通大学博士学位论文摘要AbstractWiththedevelopmentofmarketeconomyandlogisticstechnology,physicaldist

8、ributionbusinessdevelopedrapidly．Inph)，sicaldistributionbusiness，thevehicleschedulingproblemaffectsmostlyonraisingservicequality,reducinglogisticscostandincreasingeconomicbenefitsofphysicaldistributionenterprises．Indailylifeandpr