PDF《G06Q 10/00 (2006.01)》

[19]中华人民共和国国家知识产权局 [12]发明专利申请公布说明书 [11]公开号 CN 101159048A [43]公开日 2008年4月9日[21]申请号 200710176838.

6 [22]申请日 2007.11.05 [21]申请号 200710176838.6 [71]申请人 朱道立 地址 200433上海市国顺路670号复旦大学管理 学院 共同申请人 叶耀华 戴锡 吴勤F [72]发明人 朱道立 叶耀华 戴锡 吴勤F [74]专利代理机构 北京双收知识产权代理有限公司 代理人 解政文 [51]Int.CI. G06Q 10/00 (2006.01) G06Q 50/00 (2006.01) 权利要求书

6 页 说明书

21 页 附图

8 页[54]发明名称 油品配送槽车调度系统及其方法 [57]摘要 本发明油品配送槽车调度的方法,针对油品资 源和运输资源,包括分派槽车、分配舱位、指定发 油油库和编排槽车行车路径,应用Socket通讯方式, 通过物流信息系统采集基本数据,并采用建立数学 模型、用于满足约束要求的第一调度方案和用于完 成对该调度方案进行优化的第二调度方案,进行整 体优化和集中调度.其优点是:该方法综合考虑多 车场、多车型、多油库、多油品、多舱位、行车约 束、配载约束及工作量均衡各因素,显著降低了配 送成本,提高了调度决策的效率,提升了管理的快 速反应水平,可将加油站提交补货订单的截止时间 推迟2个小时.这一集中优化决策显著提高了石油 销售公司的扁平化集中式管理水平. 200710176838.6 权利要求书第1/6页21. 一种油品配送槽车调度的方法,该方法对油品配送系统实施油品配送槽车的低成本调 度,所述油品配送系统包括若干油库、加油站、承运车队的槽车和利用GPS 、GIS 、液位仪、 Internet的物流信息系统,其特征在于,该方法执行如下步骤: 第1步,设置配送槽车调度区域,进入第2步;

第2 步,应用Socket 通讯方式,通过物流信息系统采集用于槽车调度的基本数据并将 所采集的数据保存于本地数据库,进入第3步;

第3 步,进行本地数据库参数表的参数设置,然后依次进入第4 步和第5 步,执行用于满足约束要求的第一调度方案和用于完成对该调度方案进行优化的第二调度方案;

第4 步,执行所述第一调度方案,完成满足约束要求的槽车调度方案,执行如下步骤: (1) 将已被列入槽车行车路径的补货订单标记为 已编排 ,在剩下的补货订单中, 将最高配送优先级的补货订单标记为 待编排 ,其余补货订单标记为 暂不编排 ;

将所 有槽车标记为 未饱和 ,进入步骤(2);

(2) 如果所有补货订单的标记均为 已编排 ,则输出调度方案,本算法结束;

否则, 进入步骤(3);

(3) 如果不存在标记为 待编排 的补货订单,则清除所有补货订单的标记,返回步骤(1);

否则,进入步骤(4);

(4) 如果所有槽车均已标记为 已饱和 ,则添加一辆虚拟槽车,并将其标记为 未 饱和 ,进入步骤(5);

(5) 在 未饱和 槽车集合中,根据槽车分派优先级选择槽车,记为k ,进入步骤(6) ;

(6) 从 待编排 补货订单集合中筛选出一个子集作为种子订单集,进入步骤(7) ;

(7) 如果种子订单集为空集,则将槽车k 标记为 已饱和 ,返回步骤(4) ;

否则,进入步骤(8);

(8) 对种子订单集中的每个补货订单,以槽车k 的始发车场坐标为原点,向补货订单 的收货加油站坐标发出的射线为极轴,在沿逆时针扫描α弧度所形成的扇形区域内,统计 其覆盖的 待编排 补货订单个数作为该补货订单的覆盖数,然后进入步骤(

9 ) ;

(9) 在种子订单集中,选择覆盖数最大的补货订单作为种子订单,进入步骤(10) ;

(10) 以槽车k 的始发车场坐标为原点,向种子订单的收货加油站坐标发出的射线为极轴,在由此构成的极坐标系中,按照补货订单的收货加油站地理坐标的极角从小到大的 顺序,逐个考察 待编排 补货订单集合中的每个补货订单,更新槽车k 的行车路径并返 200710176838.6 权利要求书第2/6页3回步骤(3);

第5 步,执行所述第二调度方案,完成对上述满足约束要求的槽车调度方案的优化, 执行如下步骤: (1)将Completed的值设置为1;

(2) 应用2- 替换法进行搜索,如果搜索到更优调度方案,则用其替换原槽车调度方案, 并将Completed的值置为0;

否则,进入步骤(3);

(3) 应用跨路径边替换法进行搜索,如果搜索到更优调度方案,则用其替换原槽车调 度方案,并将Completed的值置为0;

否则,进入步骤(4);

(4) 应用订单重新分配法进行搜索,如果搜索到更优调度方案,则用其替换原槽车调 度方案,并将Completed的值置为0;

否则,进入步骤(5);

(5) 如果Completed 的值为1 , 则输出槽车调度方案,进入第6 步;

否则,返回步骤(1);

第6 步,对优化的槽车调度方案进行人工确认,如果确认不通过,则进入第7 步;

否则,进入第8步;

第7 步,对槽车调度方案进行人工修改,完成槽车调度方案的修改之后,返回第4 步;

第8 步,输出槽车调度方案,将槽车调度方案保存于本地数据库,最后,程序终止. 2. 根据权利要求1 所述的方法,其特征在于,其中在所述第2 步中,由所述物流信息 系统采集的数据如下: (1)有关油品和配送区域内的加油站、油库及槽车的基本数据;

(2) 加油站和油库的经纬度坐标、道路里程、槽车可通行道路、槽车行车区域、槽车 返回车场、道路路桥费;

(3) 加油站、油库和车辆的实时数据,包括:油库储油量、油品密度、补货订单、车 况信息.

3 . 根据权利要求1 或2 所述的方法,其特征在于,其中在所述第5 步(

3 ) 中,所述应用跨路径边替换法进行搜索,执行如下步骤: (1) 从原调度方案的行车路径内终止端点为加油站的边中,按照边上的行车费用从大到小的顺序,选出ψ1 条边;

当行车路径内终止端点为加油站的边数小于ψ3 时,则将这些 边全选,将选出的这些边所构成的集合记为 (2)自集合 中选取被替换的边,且它们所在的行车路径不多于ψ2 条,每条行车路 200710176838.6 权利要求书第3/6页4径中被替换的边不多于ψ3 条;

(3) 用满足约束的边对选出被替换的边进行替换,并对在替换形成的行车路径中所包含的补货订单,重新分配槽车舱位和确定计划配送量,重新指定发油油库和选择槽车的 返回车场. 4. 根据权利要求3 所述的方法,其特征在于,其中在所述第5 步(4) 中,所述应用订单重新分配法进行搜索,执行如下步骤: (1) 从原调度方案的行车路径内表示加油站的点中,按照点的节约成本从大到小的顺 序,选出_1 个点;

当行车路径内表示加油站的点数小于_1 时,则将这些点全选,将选出的 这些点所构成的集合记为 (2)自集合 中选取重新分配的点,且它们所在的行车路径不多于_2 条,每条行车 路径中被重新分配的点不多于_3 个;

(3) 应用最小成本插入法对选出被重新分配的点进行重新分配和路径插入,并对在替 换形成的行车路径中所包含的补货订单,重新分配槽车舱位和确定计划配送量,重新指定 发油油库和选择槽车的返回车场. 5. 根据权利要求4 所述的方法,其特征在于,其中所述第7 步,对槽车调度方案进行人 工修改包括: (1) 对作业点进行修改,即订单的装/ 卸油作业在车辆配送路径中进行重新定位,即: 将一条路径中的作业点移出,再移入另一条路径或同一路径的其它位置,由于修改必是可行, 因此还需做可行性检验和处理之后,再应用第一调度方案和第二调度方案做进一步的改进;

而对于前序约束、订单与车辆舱位的匹配条件这些简单约束的可行性检验,可放在修改过程 中进行;

(2)对车辆或作业点施加 加锁 标记. 6. 根据权利要求5 所述的方法,其特征在于,其中所述第8 步,所述输出槽车调度方案, 将槽车调度方案保存于本地数据库,所更新的数据项分别是: (1) 补货订单数据表中的数据项:计划配送量,分派槽车编号,装载舱位编号,发油 油库编号;

(2) 槽车行车路径数据表中的数据项:槽车编号,油库或加油站的结点类型,结点编 号,到达结点的次序序号,执行订单编号. 200710176838.6 权利要求书第4/6页57. 一种油品配送系统,其特征在于,包括若干油库、加油站、承运车队的槽车和利用 GPS 、GIS 、液位仪、Internet 的物流信息系统,以及一计算机,所述物流信息系统采集的 数据输入到计算机,计算机输出对油库、加油站和槽车的调度信息,计算机的油品配送方 法执行如下步骤: 第1步,设置配送槽车调度区域,进入第2步;

第2 步,应用Socket 通讯方式,通过物流信息系统采集用于槽车调度的基本数据并将 所采集的数据保存于本地数据库,进入第3步;

第3 步,进行本地数据库参数表的参数设置,然后依次进入第4 步和第5 步,执行用于满足约束要求的第一调度方案和用于完成对该调度方案进行优化的第二调度方案;

第4 步,执行所述第一调度方案,完成满足约束要求的槽车调度方案,执行如下步骤: (1) 将已被列入槽车行车路径的补货订单标记为 已编排 ,在剩下的补货订单中, 将最高配送优先级的补货订单标记为 待编排 ,其余补货订单标记为 暂不编排 ;

将所 有槽车标记为 未饱和 ,进入步骤(2);

(2) 如果所有补货订单的标记均为 已编排 ,则输出调度方案,本算法结束;

否则, 进入步骤(3);

(3) 如果不存在标记为 待编排 的补货订单,则清除所有补货订单的标记,返回步骤(1);

否则,进入步骤(4);

(4) 如果所有槽车均已标记为 已饱和 ,则添加一辆虚拟槽车,并将其标记为 未 饱和 ,进入步骤(5);

(5) 在 未饱和 槽车集合中,根据槽车分派优先级选择槽车,记为k ,进入步骤(6) ;

(6) 从 待编排 补货订单集合中筛选出一个子集作为种子订单集,进入步骤(7) ;

(7) 如果种子订单集为空集,则将槽车k 标记为 已饱和 ,返回步骤(4) ;

否则,进入步骤(8);

(8) 对种子订单集中的每个补货订单,以槽车k 的始发车场坐标为原点,向补货订单 的收货加油站坐标发出的射线为极轴,在沿逆时针扫描α弧度所形成的扇形区域内,统计 其覆盖的 待编排 补货订单个数作为该补货订单的覆盖数,然后进入步骤(

9 ) ;

(9) 在种子订单集中,选择覆盖数最大的补货订单作为种子订单,进入步骤(10) ;

(10) 以槽车k 的始发车场坐标为原点,向种子订单的收货加油站坐标发出的射线为极轴,在由此构成的极坐标系中,按照补货订单的收货加油站地理坐标的极角从小到大的 顺序,逐个考察 待编排 补货订单集合中的每个补货订单,更新槽车k 的行车路径并返 200710176838.6 权利要求书第5/6页6回步骤(3);

第5 步,执行所述第二调度方案,完成对上述满足约束要求的槽车调度方案的优化, 执行如下步骤: (1)将Completed的值设置为1;

(2) 应用2- 替换法进行搜索,如果搜索到更优调度方案,则用其替换原槽车调度方案, 并将Completed的值置为0;

否则,进入步骤(3);

(3) 应用跨路径边替换法进行搜索,如果搜索到更优调度方案,则用其替换原槽车调 度方案,并将Completed的值置为0;

否则,进入步骤(4);

(4) 应用订单重新分配法进行搜索,如果搜索到更优调度方案,则用其替换原槽车调 度方案,并将Completed的值置为0;

否则,进入步骤(5);

(5) 如果Completed 的值为1 , 则输出槽车调度方案,进入第6 步;

否则,返回步骤(1);

第6 步,对优化的槽车调度方案进行人工确认,如果确认不通过,则进入第7 步;

否则,进入第8步;

第7 步,对槽车调度方案进行人工修改,完成槽车调度方案的修改之后,返回第4 步;

第8 步,输出槽车调度方案,将槽车调度方案保存于本地数据库,最后,程序终止. 8. 根据权利要求7 所述的系统,其特征在于,其中在所述第2 步中,由所述物流信息系 统采集的数据如下: (1)有关油品和配送区域内的加油站、油库及槽车的基本数据;

(2) 加油站和油库的经纬度坐标、道路里程、槽车可通行道路、槽车行车区域、槽车 返回车场、道路路桥费;

(3) 加油站、油库和车辆的实时数据,包括:油库储油量、油品密度、补货订单、车 况信息.

9 . 根据权利要求7 或8 所述的系统,其特征在于,其中在所述第5 步(

3 ) 中,所述应用跨路径边替换法进行搜索,执行如下步骤: (1) 从原调度方案的行车路径内终止端点为加油站的边中,按照边上的行车费用从大到小的顺序,选出ψ1 条边;

当行车路径内终止端点为加油站的边数小于ψ3 时,则将这些 边全选,将选出的这些边所构成的集合记为 (2)自集合 中选取被替换的边,且它们所在的行车路径不多于ψ2 条,每条行车路 200710176838.6 权利要求书第6/6页7径中被替换的边不多于ψ3 条;

(3) 用满足约束的边对选出被替换的边进行替换,并对在替换形成的行车路径中所包含的补货订单,重新分配槽车舱位和确定计划配送量,重新指定发油油库和选择槽车的 返回车场.

1 0 . 根据权利要求9 所述的系统,其特征在于,其中在所述第5 步(

4 ) 中,所述应用订单重新分配法进行搜索,执行如下步骤: (1) 从原调度方案的行车路径内表示加油站的点中,按照点的节约成本从大到小的顺 序,选出_1 个点;

当行车路径内表示加油站的点数小于_1 时,则将这些点全选,将选出的 这些点所构成的集合记为 (2)自集合 中选取重新分配的点,且它们所在的行车路径不多于_2 条,每条行车 路径中被重新分配的点不多于_3 个;

(3) 应用最小成本插入法对选出被重新分配的点进行重新分配和路径插入,并对在替 换形成的行车路径中所包含的补货订单,重新分配槽车舱位和确定计划配送量,重新指定 发油油库和选择槽车的返回车场. 11. 根据权利要求10 所述的方法,其特征在于,其中所述第7 步,对槽车调度方案进行 人工修改包括: (1) 对作业点进行修改,即订单的装/ 卸油作业在车辆配送路径中进行重新定位,即: 将一条路径中的作业点移出,再移入另一条路径或同一路径的其它位置,由于修改必是可行, 因此还需做可行性检验和处理之后,再应用第一调度方案和第二调度方案做进一步的改进;

而对于前序约束、订单与车辆舱位的匹配条件这些简单约束的可行性检验,可放在修改过程 中进行;

(2)对车辆或作业点施加 加锁 标记. 12. 根据权利要求11 所述的系统,其特征在于,其中所述第8 步,所述输出槽车调度方 案,将槽车调度方案保存于本地数据库,所更新的数据项分别是: (1) 补货订单数据表中的数据项:计划配送量,分派槽车编号,装载舱位编号,发油 油库编号;

(2) 槽车行车路径数据表中的数据项:槽车编号,油库或加油站的结点类型,结点编 号,到达结点的次序序号,执行订单编号. 200710176838.6 说明书第1/21页8油品配送槽车调度系统及其方法 技术领域 本发明涉及信息技术应用领域,特别涉及一种油品配送槽车调度系统及其方法.背景技术 油品配送槽车调度,是石油销售公司在获取加油站的补货需求后,根据当时的运输资源和储油量,调度槽车完成从油库到加油站的油品补给配送任务,包括:将补货订单分配给槽车并指定其发油油库,以及编排槽车的行车路径.其计划编制质量直接决定了油品配送运输成本、槽车舱位利用率和加油站安全库存补货率. 目前,在我国成为世贸组织(WTO)成员................