一种多类型场所中的带时间窗路径规划方法

本发明公开了一种多类型场所中的带时间窗路径规划方法，基于定义的在多类型场所中的带时间窗旅行商问题M‑TSPTW及目标函数，该方法包括四个阶段：将节点按照地点和时间分类，基于只能在某一天访问的节点，得到旅行商每天的初始路径；检索初始路径的空闲时间，若多天时间窗节点的开放时间与空闲时间有重叠，将节点插入到对应位置；针对未能成功插入到路径中的节点，基于当前路径的空闲时间进行邻域搜索，通过多次替换将多天时间窗节点添加到路径中，形成新路径；对新路径进行扰动以减少最终路径的总长度，只改变某一天节点的访问次序，或选取并交换某两天路径中的节点。本发明针对目前求解硬时间约束M‑TSPTW精确算法消耗时间过长的问题，提供了部分固定策略和基于时间的邻域搜索策略，减轻计算量又准确判断了问题的可行性。