物流配送调度算法分析

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