物流配送调度算法分析

1,物流配送调度算法分析,2020年6月5日,2,Topics,问题描述算法输入条件分析算法输出分析算法指标算法异常处理算法框架百度地图接口调研,3,问题描述,问题背景：1.城市中有固定的货运公交站点，货运公交运行于各个站点间，并且可在各个站点进行装货和卸货。2.通常在派发调度任务时，货运路线的信息是已知的。货运车辆的数量和车辆起点（位置）是已知的。但是车辆运行时间和路线需要算法确定。算法确定的车辆起始和终点是否可以不同？已经解决：起始点与线路相同，终点可以设置（1,线路起始点，线路终点，可停车的站点）,4,问题描述,3.每个货运站点需要装载或者卸载的货物有重量、体积、数量、性质等信息，同时指定了的货运公交到达时间（货运公交车需要在此时间之前到达）。4.货物送到货运站点然后再送到指定的客户。算法需要根据客户地址确定该客户订单对应的最近的货运站点5.调度任务通常一天会派发两次（上午，下午各一次）。算法运行时间需要控制在2小时左右。（根据地图规模，站点数量等指标来确定。）,5,问题描述,调度策略考虑的因素有：（1）各个货运站点的发货信息和收货信息、收发货时间等。（2）货运公交的信息；（3）道路信息；,6,问题描述,调度策略满足：发出车量尽可能少，车辆装载率高而空车率低，在满足上述需求基础上进一步考虑车辆运行里程的优化。装载率=实际装载量/总装载能力*100%空车率=空车行走距离/配送的总距离*100%,7,算法输入条件分析1.线路基本信息,8,算法输入条件分析2.车辆设置,9,算法输入条件分析3.送货策略设置（重点）,10,算法输入条件分析4.伙伴排序依据（具体含义？,11,算法输入条件分析5.契合时间窗的方式,12,算法输入条件分析6.数据信息,6.1运单信息货物名称、数量、体积、重量、发货/收货、常温/冷藏、货物属性、产生时间、可接收时间、卸货/装货耗时，起始站点、目标站点。相同类型的运输任务可以同车；可接收时间为目标站点可以接收订单的时间范围。,13,算法输入条件分析6.数据信息,6.2道路信息名称、地址范围、距离、单（双）向、所属区划、交叉点。道路级别及车速限制：州际、主干道路、次级道路、地方道路和坡道，各级别道路对应的车速及浮动量。道路限制:车型限制、单行道、高峰时间、高峰时间、高峰时车速、封路区域、封路时间、车牌单双号等此部分信息需要从GIS数据中拿到。,14,算法输入条件分析6.数据信息,6.3站点信息货运节点地理信息节点的经纬度值。节点属性(取和送)。(出发节点、返回节点、其他)。节点的车辆类型限制m种车型。,15,算法输出,16,算法指标,17,异常情况,18,算法框架,算法框架包括主要三个部分：1.根据系统的运输线路设置和约束条件获取该运输线路的伙伴站点。2.根据伙伴站点的数量和约束条件确定运输的车辆。3.根据车辆的运单和约束条件对运输路径调整。,19,算法框架,1.根据系统的运输线路设置和约束条件获取该运输线路的伙伴站点。计算每条线路从起点到终点的最短路径。用插入法比较加入一个新的运单之后，最短路径的变化，选择最优的站点进入到路线中。运行一段时间之后可以将插入法和历史数据结合考虑。从而获取更加合适的伙伴集合。重复上述过程得到各个线路对应的运单集合。,20,算法框架,2.根据伙伴站点的数量和约束条件确定运输的车辆。对伙伴站点按照到达时间的先后排序，按照顺序安排运单，主要考虑的因素有：运单是否满足时间需要；运单的距离因素；车辆的装载和空车；需要定义一个约束函数来计算。,21,算法框架,3.根据车辆的运单和约束条件对运输路径调整。在各个车辆的运输任务确定之后根据运单的情况来确定最短路径。此时问题简化为旅行商问题（TSP）。考虑用启发式算法，增加历史数据的参考。也可以对比各种经典算法，选择合适的。,22,百度开发接口调研,基本数据信息有，没有找到的信息：各级别道路对应的车速及浮动量。（需要落实）道路限制:车型限制、单行道、高峰