论文部分内容阅读
随着我国经济高速发展,人民生活水平不断提高,物流配送行业也得到了快速发展,但配送企业等运输类企业一直面临着配送成本过高的问题。智能车辆路径规划能有效解决运输过程中路线规划不合理、运输延误率高等问题,可以极大地降低配送成本。并且,物流配送环节在实际运作过程中存在着大量随机因素,同时客户还会对货物送达时间提出软性要求。因此对充分考虑上述因素的带软时间窗的随机车辆路径问题（Stochastic Vehicle Routing Problem with Soft Time Window,SVRPSTW）进行研究和优化更具实际意义。本文以SVRPSTW问题为基础,对需求量随机的VRPSTW、需求量和服务时间随机的VRPSTW、行驶时间和服务时间随机的VRPSTW进行了研究,并提出了相应的优化模型和求解算法。本文研究工作包括以下三个方面:（1）针对需求量随机的VRPSTW问题（Vehicle Routing Problem with Stochastic Demand and Soft Time Window,VRPSD-STW）,本文以规划时间最短、修正成本最少、违背约束最小为目标建立了一种新的随机规划模型,并提出了一种两阶段算法。第一阶段将客户随机需求作确定化处理,使其等于期望值;然后,引入自适应禁忌长度、自适应惩罚系数及改进邻域结构以解决车辆偏离软时间问题,最后得到初步的规划方案,但该方案仍存在一定的误差。第二阶段采用SRTD算法（Select Return To Depot）修正第一阶段所得初步规划方案的误差。实验结果表明,改进后的两阶段算法具有较强的寻优能力、较高的鲁棒性,且能够快速地找到合理的解决方案。（2）针对需求量和服务时间随机的VRPSTW问题（Vehicle Routing Problem with Stochastic Demand and Stochastic Service Time with Soft Time Window,VRPSDSSTSTW）,本文综合考虑车辆行驶成本和客户服务水平,以配送车辆行驶路径为研究对象,建立了一种机会约束规划和两阶段随机规划相结合的数学模型。同时,根据问题特点提出了一种混合禁忌搜索算法。该算法有效结合了最近邻算法和禁忌搜索算法,将时间窗宽度及距离作为最近邻算法中的节点选择标准;并对禁忌搜索算法中禁忌长度、邻域结构等构成要素进行了改进。实验结果表明,改进后的混合禁忌搜索算法寻优能力较强、鲁棒性较高,同时算法所得车辆行驶路径受客户需求变动影响小。（3）针对行驶时间和服务时间随机的VRPSTW问题（Vehicle Routing Problem with Stochastic Travel Time and Stochastic Service Time with Soft Time Window,VRPSTTSST-STW）,本文以总成本最小化为目标,运用随机规划理论构建了带修正的随机规划模型;并根据问题特点设计了一种贪心算法与禁忌搜索算法的混合算法。采用改进贪心算法生成初始解,将禁忌搜索算法中禁忌长度进行自适应调整,引入一种由特定邻域和三种常用邻域组成的多邻域结构,避免算法陷入局部最优。实验结果表明,改进后的混合算法寻优能力较强、鲁棒性较高;且该算法相较于其他启发式算法具有一定的优越性。