一种基于滚动时域调度算法的公共慢行系统动态调度方法

摘要

一种基于滚动时域调度算法的公共慢行系统动态调度方法，包括以下步骤：1)设定时间轴表示一个工作日的整个调度周期，关键点是指正在接受服务或者有运输车辆正在前往该点的路上的租赁点，时间窗是公共自行车租赁点允许服务的时间范围，租赁点i的满意度表示为fi(ti)：2)建立调度模型；3)采用基于滚动时域的动态调度方法，将整个调度周期划分为若干个子调度周期，将每一个子调度周期看作是静态的调度问题，通过变邻域的禁忌搜索算法求解若干个静态的调度问题和不断滚动更新调度计划的方法实现动态的车辆调度。本发明种能够进行自动统计、实时性好、提升运行效率。

主权项

1.一种基于滚动时域调度算法的公共慢行系统动态调度方法，其特征在于：所述公共慢行系统动态调度方法包括以下步骤：1)、设定时间轴表示一个工作日的整个调度周期，在时间轴上，每一个时刻对应一个场景，关键点是指正在接受服务或者有运输车辆正在前往该点的路上的租赁点，关键点的任务是不能更改；时间窗是公共自行车租赁点允许服务的时间范围，用模糊时间窗来描述租赁点对服务时间的约束范围，[WA_i，WB_i]表示租赁点i可容忍的服务时间范围，[WC_i，WD_i]表示租赁点i期望的服务时间范围，t_i表示车辆到达点i的时间；租赁点i的满意度表示为：2)、建立调度模型：停车场P0有T辆运输车，运输车辆k最大载重量为Q_k，从停车场P0派遣若干运输车辆向n个公共自行车租赁点提供服务，每一个租赁点的容量为E_i(i＝1，2…n)，在t时刻，每个租赁点的自行车的数量为q_i(t)(i＝1，2……n)；q_i(t)与E_i之比为H_i(t)，正常状态下租赁点i的H_i的范围是[C_min，C_max]，租赁点的服务请求有两种情况：①当H_i(t)＞C_max时，表示租赁点在t时刻需要运出自行车；②当H_i(t)＜C_min时，表示租赁点在t时刻需要运入自行车；租赁点i可容忍的服务时间范围是[WA_i，WB_i]，期望的服务时间范围是[WC_i，WD_i]；租赁点i的服务时间为s_i，t_i表示运输车辆到达租赁点i开始服务的时间，f_i(t_i)表示租赁点i的满意度；租赁点的需求量为租赁点需要运入或运出的自行车的数量，当H_i(t)＞C_max时，租赁点需运出自行车，设租赁点此时的需求量为d_i(t)，当租赁点接受服务后，其H_i应该在区间[C_min，C_max]内，则必须满足$C_{\min }\le \frac{q_i\left(t\right)-d_i\left(t\right)}{E_i}\le C_{\max },$即q_i(t)-C_maxE_i≤d_i(t)≤q_i(t)-C_minE_i，此时，d_i(t)取其下限q_i(t)-C_maxE_i即可满足要求；同理，当H_i(t)＜C_min时，d_i(t)＝C_minE_i-q_i(t)；N(t)：t时刻，所有未完成任务租赁点，新的有服务请求的租赁点和停车场的集合；M(t)：t时刻，所有关键点、未完成任务租赁点，新的有服务请求的租赁点和停车场的集合；K：运输车辆的集合；TS：时间轴；Q_ki：运输车辆K在租赁点i服务后装载的自行车的数量；以租赁点总的满意度最大化为目标建立公共慢行系统调度的模型，目标函数如下：$\max Z=\underset{t\in \mathrm{TS}}{\Sigma }\underset{i\in N\left(t\right)}{\Sigma }\left[f_i\left(t_i\right)\right]---\left(1\right)$约束条件为：Q_ki＜Q_k$\forall i\in M\left(t\right),k\in K---\left(2\right)$3)、将整个调度周期划分为若干个子调度周期，将每一个子调度周期看作是静态的调度问题，通过求解若干个静态的调度问题和不断滚动更新调度计划的方法实现动态的车辆调度；在求解每子调度周期对应的静态调度问题时，采用基于变邻域的禁忌搜索算法获取调度计划；在变邻域的搜索过程中存在以下概念：(a)变邻域搜索条件：当搜索过程中连续若干次迭代后解的适配值没有提高时，满足变邻域搜索条件，否则，不满足变邻域搜索跳条件；(b)原邻域解：禁忌搜索过程中不满足变邻域搜索条件时的邻域解；(c)变邻域解：禁忌搜索过程中满足变邻域搜索条件时的邻域解，变邻域解与原邻域解相比具有不同的邻域结构。变邻域的禁忌搜索算法步骤如下所示，包括：(3.1)产生初始解，初始化参数和禁忌表；(3.2)判断是否满足终止条件，如果满足则介绍并输出结果，否则，转至步骤(3.3)；(3.3)判断是否满足变邻域条件，如果满足生成当前解的变邻域解，反之，生成当前解的原邻域解；(3.4)确定候选解；(3.5)判断是否满足藐视准则，如果是，则用特赦解替换当前解，转至步骤(3.2)并更新禁忌表，否则，则转至步骤(3.6)；(3.6)在候选解中用最优的非禁忌解替换当前解，并更新禁忌表，转至步骤(3.2)。