物流配送调算法分析.pptx

1Topics问题描述算法输入条件分析算法输出分析算法指标算法异常处理算法框架百度地图接口调研第1页/共23页2问题描述问题背景：1.城市中有固定的货运公交站点，货运公交运行于各个站点间，并且可在各个站点进行装货和卸货。2.通常在派发调度任务时，货运路线的信息是已知的。货运车辆的数量和车辆起点（位置）是已知的。但是车辆运行时间和路线需要算法确定。算法确定的车辆起始和终点是否可以不同？已经解决：起始点与线路相同，终点可以设置（1,线路起始点，线路终点，可停车的站点）第2页/共23页3问题描述3.每个货运站点需要装载或者卸载的货物有重量、体积、数量、性质等信息，同时指定了的货运公交到达时间（货运公交车需要在此时间之前到达）。4.货物送到货运站点然后再送到指定的客户。算法需要根据客户地址确定该客户订单对应的最近的货运站点5.调度任务通常一天会派发两次（上午，下午各一次）。算法运行时间需要控制在2小时左右。（根据地图规模，站点数量等指标来确定。）第3页/共23页4问题描述调度策略考虑的因素有：（1）各个货运站点的发货信息和收货信息、收发货时间等。（2）货运公交的信息；（3）道路信息；第4页/共23页5问题描述调度策略满足：发出车量尽可能少，车辆装载率高而空车率低，在满足上述需求基础上进一步考虑车辆运行里程的优化。装载率=实际装载量/总装载能力*100%空车率=空车行走距离/配送的总距离*100%第5页/共23页6算法输入条件分析1.线路基本信息 线线 路路基基本本信信息息设设置置 预期出发时间、预期出发时间、每条线路可以单独设置，每条线路可以单独设置，也可以设置一个值供所也可以设置一个值供所有线路使用有线路使用预期运行时间、预期运行时间、最长运行时间最长运行时间线路经过的站点数量限制线路经过的站点数量限制出发前后和货运站点交接时出发前后和货运站点交接时间间 每个站点可以有自己的每个站点可以有自己的交接时间也可以设置一交接时间也可以设置一个值供所有站点使用个值供所有站点使用线路与车辆关系线路与车辆关系每条线路可以有多辆车参与每条线路可以有多辆车参与运输任务，运输任务，车辆的终点车辆的终点可以是可以是(1)线路终点线路终点(2)线线路起点路起点.(3)可停车的中间可停车的中间站点。站点。第6页/共23页7算法输入条件分析2.车辆设置2.2.车车辆辆设设置置车辆容积限制标准（体积、重量、两者同时考虑、车辆容积限制标准（体积、重量、两者同时考虑、其他单位）其他单位）每辆车辆需要单每辆车辆需要单独设置限制标准独设置限制标准提供车辆类型及每种类型的数量提供车辆类型及每种类型的数量每条线路的出发每条线路的出发点都应该有此信点都应该有此信息息车辆使用时的优先顺序或者车辆使用时的优先顺序或者系统自行比较车辆的组合方式。系统自行比较车辆的组合方式。默认自有车辆优先默认自有车辆优先每一辆车的起始站点、结束站点、发车时间每一辆车的起始站点、结束站点、发车时间起始点已知，结束起始点已知，结束点，发车时间由点，发车时间由算法确定。算法确定。车牌（有些道路在特定日期限制单（双）车牌）车牌（有些道路在特定日期限制单（双）车牌）仅仅在路线规划仅仅在路线规划中使用中使用第7页/共23页8算法输入条件分析 3.送货策略设置（重点）3.3.送货策送货策略设置略设置A.A.大宗货物优先：先送最大宗货物，大宗货物优先：先送最大宗货物，卸下后能减少后面路线的车行油卸下后能减少后面路线的车行油耗。耗。默认为默认为D项。项。A,B,C项可以项可以与与D,E项组合项组合使用。使用。B.B.紧急订单优先：需要把紧急订单紧急订单优先：需要把紧急订单先送掉；先送掉；C.C.最远客户优先（最近客户优先）最远客户优先（最近客户优先）D.D.行驶距离优先；行驶距离优先；E.E.运行的时间优先；运行的时间优先；第8页/共23页9算法输入条件分析4.伙伴排序依据（具体含义？4.4.伙伙伴伴排排序序依依据据初始点初始点暂时不考虑）暂时不考虑）中心中心暂时不考虑）暂时不考虑）最近站点最近站点暂时不考虑）暂时不考虑）第9页/共23页10算法输入条件分析5.契合时间窗的方式5.5.契契合合时时间间窗窗的的方方式式线路出发时间是否允许调整、调整范围线路出发时间是否允许调整、调整范围（根据（根据车辆调整更合适，默认也可以应用于该线车辆调整更合适，默认也可以应用于该线路中的所有车辆）路中的所有车辆）由线路中各个站由线路中各个站点的时间与车点的时间与车辆到达的时间辆到达的时间差来决定差来决定调整到达次序调整到达次序仅仅在线路内部仅仅在线路内部调整调整调整等待时间调整等待时间(不能为负数不能为负数)仅仅在线路内部仅仅在线路内部调整调整增加或者减少任务增加或者减少任务减少的任务将直减少的任务将直接删除。增加接删除。增加的任务如果出的任务如果出现不满足的情现不满足的情况将提醒。况将提醒。第10页/共23页11算法输入条件分析6.数据信息6.1 运单信息货物名称、数量、体积、重量、发货/收货、常温/冷藏、货物属性、产生时间、可接收时间、卸货/装货耗时，起始站点、目标站点。相同类型的运输任务可以同车；可接收时间为目标站点可以接收订单的时间范围。第11页/共23页12算法输入条件分析6.数据信息6.2道路信息名称、地址范围、距离、单（双）向、所属区划、交叉点。道路级别及车速限制：州际、主干道路、次级道路、地方道路和坡道，各级别道路对应的车速及浮动量。道路限制:车型限制、单行道、高峰时间、高峰时间、高峰时车速、封路区域、封路时间、车牌单双号等此部分信息需要从GIS数据中拿到。第12页/共23页13算法输入条件分析6.数据信息6.3 站点信息货运节点地理信息 节点的经纬度值。节点属性(取和送)。(出发节点、返回节点、其他)。节点的车辆类型限制 m种车型。第13页/共23页14算法输出1.1.路线路线站点（按到达顺序排序）站点（按到达顺序排序）序号，站点描述、序号，站点描述、站点地址、立方、时间段表（希望时间站点地址、立方、时间段表（希望时间与预计到达时间）与预计到达时间）。输出界面上可以。输出界面上可以进行手动微调。进行手动微调。手动微调是仅限于手动微调是仅限于线路内部调整吗线路内部调整吗？如果有节点删？如果有节点删除，删除节点怎除，删除节点怎么处理？么处理？2.2.地图显示地图显示a.a.地图上显示站点的运输顺序地图上显示站点的运输顺序;b.;b.车辆行驶车辆行驶路径信息，包括各个车辆经过的道路、路径信息，包括各个车辆经过的道路、车辆在停靠站点以及各个站点停靠的时车辆在停靠站点以及各个站点停靠的时间。上述路径信息可最终向用户显示出间。上述路径信息可最终向用户显示出时段图、配送路线、线路播放时段图、配送路线、线路播放地图显示需要地理地图显示需要地理系完成，并需要系完成，并需要确定好接口；车确定好接口；车辆运行路线的存辆运行路线的存储及显示需要与储及显示需要与GISGIS系统沟通系统沟通3.3.调度统计调度统计信息信息调配车辆数目，总里程数、理论上的总费用、调配车辆数目，总里程数、理论上的总费用、每辆行驶里程数、理论上的成本及费用每辆行驶里程数、理论上的成本及费用（油耗等）（油耗等）第14页/共23页15算法指标1.1.装装载载率率，空空车车率率，无无贡贡献献时时长长装载率装载率=85%=85%；空车率；空车率=20%=20%；无贡献时长无贡献时长=30%=30%；等待时长；等待时长/总时长总时长2.2.规模规模支撑业务量为支撑业务量为500500个节点、个节点、100000100000票托运单、票托运单、15001500辆辆车；运行时间不大于车；运行时间不大于2 2小时。小时。第15页/共23页16异常情况1.1.运单量运单量运单量超出车辆运力。运单量超出车辆运力。运输时间不满足，运输时间不满足，当选用最合适当选用最合适的车尽最快速的车尽最快速度运输，到达度运输，到达时间不满足时时间不满足时报警；报警；2.2.运单时间运单时间运输车辆不能满足运单时间要求。运输车辆不能满足运单时间要求。运单体积过大，运单体积过大，运单体积超出运单体积超出可用车辆最大可用车辆最大容量时报警；容量时报警；3.3.单个运单单个运单运输车辆不能满足运单重量或者体积；运输车辆不能满足运单重量或者体积；提醒然后处理。提醒然后处理。运单超重。当运运单超重。当运单重量超出整单重量超出整个车辆载重限个车辆载重限制时报警。制时报警。第16页/共23页17算法框架算法框架包括主要三个部分：1.根据系统的运输线路设置和约束条件获取该运输线路的伙伴站点。2.根据伙伴站点的数量和约束条件确定运输的车辆。3.根据车辆的运单和约束条件对运输路径调整。第17页/共23页18算法框架1.根据系统的运输线路设置和约束条件获取该运输线路的伙伴站点。计算每条线路从起点到终点的最短路径。用插入法比较加入一个新的运单之后，最短路径的变化，选择最优的站点进入到路线中。运行一段时间之后可以将插入法和历史数据结合考虑。从而获取更加合适的伙伴集合。重复上述过程得到各个线路对应的运单集合。第18页/共23页19算法框架2.根据伙伴站点的数量和约束条件确定运输的车辆。对伙伴站点按照到达时间的先后排序，按照顺序安排运单，主要考虑的因素有：运单是否满足时间需要；运单的距离因素；车辆的装载和空车；需要定义一个约束函数来计算。第19页/共23页20算法框架3.根据车辆的运单和约束条件对运输路径调整。在各个车辆的运输任务确定之后根据运单的情况来确定最短路径。此时问题简化为旅行商问题（TSP）。考虑用启发式算法，增加历史数据的参考。也可以对比各种经典算法，选择合适的。第20页/共23页21百度开发接口调研基本数据信息有，没有找到的信息：各级别道路对应的车速及浮动量。（需要落实）道路限制:车型限制、单行道、高峰时间、高峰时间、高峰时车速、封路区域、封路时间、车牌单双号等有获取距离的接口有显示路径的接口没有找到GPS动态定位的接口直接嵌入到JavaScript中运行。第21页/共23页22讨论讨论第22页/共23页23感谢您的观看！第23页/共23页