ABSTRACT

In order to solve the problem of unbalanced space-time distribution of bikes in public bike rental points, four mixed integer linear programming models with time windows were established in the case of single and multiple dispatching centers by adopting two ideas of loading before unloading, and loading and unloading at the same time. The model aims at the minimum total delivery miles, where some constraints such as the supply and demand relationship of the lease point and the rated capacity of the truck are considered. Finally, Cplex is used to solve the exact solution of an example, where the truck distribution route is given, and the scheme differences of the four models are compared, so as to verify the correctness of the model.

Keywords:Public Rental Bicycle Scheduling, Multiple Depots, Unloading and Loading, Unloading after Loading, Cplex Solution

一类带时间窗的公共租赁自行车调度模型

郭小辉¹，魏明^2*，孙荣³

¹广州市丛文信息科技有限公司，广东 广州

²中国民航大学空中交通管理学院，天津

³中国移动通信集团江苏有限公司盐城分公司，江苏 盐城

收稿日期：2020年5月4日；录用日期：2020年5月15日；发布日期：2020年5月22日

摘 要

为解决公共自行车租赁点的自行车时空分布不均衡的现象，采用先装后卸和装卸一体两种思路，考虑租赁点的供需关系、卡车的额定载客量等约束条件，以总配送里程最少为目标，在单、多调度中心情形下，建立该问题的四类带时间窗混合整数线性规划模型。利用Cplex求解模型的精确解，结合一个算例，比较四类模型的方案差异，并给出了卡车配送路线，从而验证模型的正确性。

关键词 :公共租赁自行车调度，多调度中心，装卸一体，先装后卸，Cplex求解

Copyright © 2020 by author(s) and Hans Publishers Inc.

This work is licensed under the Creative Commons Attribution International License (CC BY 4.0).

http://creativecommons.org/licenses/by/4.0/

1. 引言

公共租赁自行车作为一种新型的交通方式，兼有公共交通和慢行交通的特点，越来越受到人们的青睐。由于城市的功能布局、经济发展差异，这引起租赁网络上的公共自行车供需关系在时间和空间上的不平衡，依靠人工调度方式几乎不可能在短时间内理顺它们之间的关系，进而不能将部分租赁点的多余自行车合理地提前调配至缺少自行车的租赁点，调度方式较粗放、低效率，可能出现部分租赁点的无车可借或车辆空闲、还车时车位已满等现象。因此，公共租赁自行车调度问题日渐突出 [1] [2]。

公共租赁自行车调度(Rental Bicycle Dispatching Problem，简称RBDP)属于车辆路径问题(Vehicle Routing Problem，简称VRP)的研究范畴，它们之间共性在于合理安排车辆访问客户或租赁点，其差异在前者考虑租赁点的装卸车辆数对供需关系影响而后者无须关注该问题，因而RBDP比VRP复杂的多，因而吸引了众多国内外学者的广泛关注。目前，RBDP分为先装后卸(卡车访问供应点装完自行车后，才访问需求点卸载自行车)、同时装卸(卡车同时访问供应或需求点，但是满足需求点的自行车需求)两种研究思路，前者比后者调度效率低，但是操作相对容易。同时装卸的RBDP的研究相对成熟，主要归纳如下：董红召等 [3] 针对公共自行车时空上分布不均衡问题，以服务点的满意度最大化为目标，建立模糊时间窗的公共慢行系统调度模型；鲍娜 [4] 系统地研究公共自行车租赁点选址决策与调度模型之间耦合关系；刘登涛等 [5] 将模拟退火算法和遗传算法混合起来求解公共自行车调度模型；张辉和郑彭军 [6] 提出了一种带模糊时间窗的城市公共自行车调度路径优化模型；徐建闽等 [7] 从时间分布和空间分布两方面分析了公共自行车高峰期潮汐需求规律及其与用地类型的关系，创新地提出以上层调度区域、调度小区和站点为主的多层次分区调度方法；胡列格等 [8] 研究公共自行车调度的车辆路径问题，并设计求解该问题的禁忌搜索算法；Szeto等研究了多车型的公共自行车调度，并设计求解大规模问题的启发式算法 [2] [9] [10]。先装后卸的RBDP的研究尚未被国内外学者深入研究，仅柳祖鹏等 [11] 借鉴货郎担问题动态规划的解题思路，研究一种先装后卸的公共自行车系统站间调度模型。由上可知，多调度中心的RBDP较少研究，既有研究均假设夜间提前调度，忽略各个租赁在不同时段的供需差异，虽然少量文献探讨配送时间窗对调度方案的影响，但是它们忽略了卡车在租赁点的装卸量是否满足供需关系，与实际不相符合。此外，现有先装后卸的RBDP不符合混合整数线性规划模型规范，无法借助Cplex等优化软件求解精确解。

综上所述，本文从运筹优化角度，针对租赁点的供需时空分布，考虑租赁点的配送时间窗因素，基于先装后卸和装卸一体两种模式，在单、多调度中心情况下，建立RBDP的四类混合整数线性规划模型。最后，以南通某区域公共租赁自行车调度为例，利用Cplex求解模型的精确解，比较了单和多调度中心、先装后卸和装卸一体的调度方案差异，从而验证模型的正确性。

2. 问题描述和数学模型

2.1. 假设

(1) 与既有智能调度平台数据交互，收集所有租赁点在各个时间段的缺少或多余自行车数；

(2) 所有供应点和需求点均在卡车配送路径中，并且只被允许一辆车访问；

(3) 忽略卡车在租赁点的装卸自行车时间对配送线路的影响。

2.2. 符号

索引：

$i,j$ ：租赁点或调度中心；

$k$ ：车辆。

集合：

$N$ ：租赁点集合；

$O$ ：调度中心集合；

$K$ ：车辆集合。

变量：

$p_j$ ：租赁点j的自行车需求量，若 $p_j>0$，则多余；否则，缺少；

$z_j$ ：租赁点j的供需标识，若 $p_j>0$，则 $z_j=1$ ；否则， $z_j=-1$ ；

$d_{ij}$ ：公共自行车租赁点i和j之间距离；

$q_i^k$ ：车辆k访问租赁点i后的自行车数量，即断面流量；

$t_i^k$ ：车辆k访问租赁点i的时间；

$\left[l_i,u_i\right]$ ：租赁点i的时间窗；

$C$ ：车辆的最大容量；

$D$ ：车辆的最大里程；

$M$ ：一个比较大的固定值。

决策变量：

$x_{ij}^k$ ：车辆k依次访问租赁点i和j；

$y_i^k$ ：车辆k是否访问租赁点i；

$p_j^k$ ：车辆k访问租赁点j时的装卸自行车数；

U_ik：辅助变量。

2.3. 目标函数

$\min {\displaystyle \underset{\forall k\in K}{\sum }{\displaystyle \underset{\forall i\in N\cup O}{\sum }{\displaystyle \underset{\forall j\in N\cup O}{\sum }{x}_{ij}^k{d}_{ij}}}}$ (1)

2.4. 约束条件

${\displaystyle \underset{\forall i\in N}{\sum }{y}_i^k}\ge 1\forall k\in K$ (2)

${\displaystyle \underset{\forall k\in K}{\sum }{y}_i^k}=1\forall i\in N\cup O\forall k\in K$ (3)

${\displaystyle \underset{\forall i\in N}{\sum }{x}_{ij}^k}={\displaystyle \underset{\forall i\in N}{\sum }{x}_{ji}^k}=y_i^k\forall j\in N,\forall k\in K$ (4)

${\displaystyle \underset{\forall i\in O}{\sum }{x}_{ij}^k}={\displaystyle \underset{\forall i\in O}{\sum }{x}_{ji}^k}=1\forall j\in N,\forall k\in K$ (5)

$U_{ik}-U_{jk}+\left(\left|H\right|*x_{ij}^k\right)\ge \left|H\right|-1,\forall i,j\in N\cup O,\forall k\in K$ (6)

$q_i^k+p_j^k-\left(1-x_{ij}^k\right)\cdot M\le q_j^k\forall i,j\in N\cup O,\forall k\in K$ (7)

$q_i^k+p_j^k+\left(1-x_{ij}^k\right)\cdot M\ge q_j^k\forall i,j\in N\cup O,\forall k\in K$ (8)

$t_i^k+T_{ij}-\left(1-x_{ij}^k\right)\cdot M\le t_j^k\forall i,j\in N\cup O,\forall k\in K$ (9)

$t_i^k+T_{ij}+\left(1-x_{ij}^k\right)\cdot M\ge t_j^k\forall i,j\in N\cup O,\forall k\in K$ (10)

$l_i\le t_i^k\le u_i\forall i,j\in N\cup O,\forall k\in K$ (11)

(12)

${\displaystyle \underset{\forall j\in N}{\sum }{x}_{0j}^k\cdot }{p}_j\ge 0\forall k\in K$ (13)

${\displaystyle \underset{\forall j\in N}{\sum }{x}_{j0}^k\cdot }{p}_j\le 0\forall k\in K$ (14)

$p_j^k\le p_j{p}_j>0\forall j\in N,\forall k\in K$ (15)

$p_j^k=p_j{p}_j<0\forall j\in N,\forall k\in K$ (16)

$q_i^k=0\forall i\in O,\forall k\in K$ (17)

$q_i^k\le C\forall i\in N,\forall k\in K$ (18)

${\displaystyle \underset{\forall i\in N\cup O}{\sum }{\displaystyle \underset{\forall j\in N\cup O}{\sum }{x}_{ij}^k{d}_{ij}}}\le D\forall k\in K$ (19)

在模型中，式(1)是问题的目标函数，追求总的出行距离最短。式(2)~(19)是约束条件，其中：式(2)和(3)表示每辆车至少访问一个租赁点、每个租赁点仅被一辆车访问；式(4)表示每个租赁点不能被多辆车访问；式(5)表示每辆车从配送中心出发并返回该配送中心；式(6)表示避免出现车辆路径子回路；式(7)和(8)表示车辆访问相邻租赁点的断面流量变化关系；式(9)和(10)表示车辆访问相邻租赁点的到达时间变化关系；式(9)和(10)表示车辆访问租赁点的到达时间满足时间窗；式(12)表示车辆访问租赁点的顺序只有一个装卸分界点；式(13)和(14)表示车辆先访问供应租赁点后访问需求租赁点；公式(15)和(16)表示车辆在租赁点装卸自行车数约束；公式(17)表示车辆由调度中心空车出发并实现空车返回调度中心；式(18)表示车辆的载客量不超过其最大额定载客量；式(19)表示车辆的行程里程不超过其上限。

有上可知，若考虑约束式(12)~(14)，该问题是先装后卸的RBDP，否则是装卸一体的RBDP；若调度中心集合O的元素为1个，是单调度中心的RBDP，否则为多调度中心的RBDP。当不考虑约束式(9)~(11)，该模型与忽略租赁点在各个时间段的自行车供需差异，可以利用夜间调度一次满足所有租赁点的整个白天供需需求。在实际使用中，根据实际问题场景，可以选择设置不同模型参数和条件。

3. 算例分析

以南通某区域的公共自行车调度为例说明，总共2个调度中心(经纬度为120.912722~31.982706和120.898025~31.984626)和29个租赁点，它们的位置、时间窗和缺少或多余自行车数如表1所示，已知配送卡车的额定载客量和最大行程里程分别为30辆自行车和15 km。

表1. 租赁点的基本信息

通过C#和Cplex搭建基于百度地图的求解框架，当配送卡车数为3、4和5时，求解RBDP在单和多调度中心、装卸一体和同时装卸的四种模型调度结果如表2所示，从中可知：(1) 随着车辆数增加，四种RBDP模型的总配送里程和时间不断增大，这是由于车辆访问客户后返回调度中心，因而增加车辆数后导致总里程和时间不一定总是减少，计算结果符合实际；(2) 无论先装后卸或装卸一体情况下，多调度中心RBDP的里程和时间均比单调度中心的少，这是因为配送卡车可以选择从较近的调度中心出发从而节省里程和时间；(3) 无论单、多调度中心情形下，装卸一体RBDP的里程和时间均比先装后卸的少，这是因为先装后卸的RBDP先集中访问供应点装车在访问需求点卸车，这必然比同时访问租赁点装卸车多绕行路线。因此，多调度中心、装卸一体的RBDP是最优的。

有上可知，车辆数为3是四种RBDP的最优方案，给出它们的最优路线如图1~图4所示。

4. 结论分析

针对先装后卸的多调度中心公共自行车调度问题，考虑满足卡车的能力约束、租赁点的供需关系等限制条件，本文建立了一类混合整数线性规划模型，通过C#调用Cplex求解一个算例表明：随着车辆数增加，单、多配送中心的总行驶里程和时间都有较轻微的增加，多调度中心相对单调度中心总里程和时间减少，计算结果符合直观分析，从而验证了模型的有效性。

本模型的研究不足在于：(1) 调度目标比较简单，忽略乘客的满意度对调度结果的影响，尤其是供应小于需求；(2) 忽略调度中心选址对调度结果的影响；(3) Cplex无法求解大规模问题，亟待寻求求解该问题的启发式算法，如：蚁群算法、遗传算法等。

图1. 单调度中心的先装后卸配送线路

图2. 多调度中心的先装后卸配送线路

图3. 单调度中心的装卸一体配送线路

图4. 多调度中心的装卸一体配送线路

表2. 四种调度模型的方案对比

基金项目

国家自然科学基金(61503201)；教育部人文社科项目(16YJCZH086, 20YJCZH176)；南通科技计划项目(MS22018012)；交通运输行业重点科技项目清单创新项目(2018-MS3-083)；江苏省六大高峰人才项目(SZCY-009)。

文章引用

郭小辉,魏 明,孙 荣. 一类带时间窗的公共租赁自行车调度模型
Dispatching Model of Public Rental Bicycle with Time Windows[J]. 交通技术, 2020, 09(03): 173-181. https://doi.org/10.12677/OJTT.2020.93021

参考文献