随着互联网和经济全球化的发展,物流在制造相关的企业中占据越来越重要的作用,如何提高生产制造速度,降低物流成本是企业关注的重要方向之一。MilkRun(循环取货)作为一种新的物流模式,在小批量、多频次的物料运输中能有效降低库存,提高车辆利用率,减少运输成本。本课题从车辆路径规划角度研究MilkRun模式下的带时间窗取送货的车辆路径规划问题(Pickup and Delivery with Time Windows,PDPTW),该问题是一个NP-hard问题,没有多项式时间复杂度的求解算法,现实中在零部件运输、快递配送等行业普遍存在该问题。目前国内外对PDPTW的研究的不多而结合Milk-Run模式的更少,因此研究Milk-Run模式下的带时间窗取送货车辆路径规划问题,具有一定的现实意义。针对带时间窗取送货车辆路径规划问题,本课题设计了大邻域搜索的改进算法,外部加入多次重启策略,使得结果更稳定。算法内部提出操作算子间自适应选择策略以及操作算子内的参数向量自适应策略以提高搜索效率和邻域多样性。本算法在Li＿100标准数据集下取得车辆数为目标的最优解,并在以平均装载率为第二目标下,与模拟退火嵌套禁忌搜索算法做对比,本算法在规则分布、随机分布以及混合分布的数据集上均能取得更优的结果。根据实际应用场景,本课题进一步拓展了上述改进大邻域搜索算法的使用场景,创新性地引入休息时间窗约束和白、夜班换班的约束。针对休息时间窗约束,通过分段讨论并设定线性惩罚函数的方式来优化算法在该时间段的路径安排。针对白/夜班换班约束,本算法采取基于时间聚类的方式,先将订单按照各天的白班和夜班各自进行聚类,然后对各自班次的订单运用上述改进大邻域搜索算法进行求解,最后对所得各个白班和夜班的路径进行联合优化。通过与遗传算法的方案对比,本算法在所得车辆数目相同的情况下,能达到更高的车辆装载率。结合上述算法,本课题设计带时间窗取送货的车辆路径规划系统。该系统后端采用SSM(Spring MVC、Spring、My Batis)框架,浏览器端基于Web GIS技术并使用百度地图API以及Echarts库进行路径和数据的展示。系统主要包含三大功能,客户的订单信息管理、路径规划安排、地图展示。系统执行过程为:后台获取有效订单在前端展示并提供增加、查询等操作,服务器对所有订单运行车辆路径规划模块进行路径规划,最后在前端将各个车辆的路线规划信息进行展示。