Operational research optimization of meituan intelligent distribution system - Notes

The authors ：Tyan Blog ：noahsnail.com  |  CSDN  |  Simple books

This article is a collection of notes for meituan's article study .

1. Meituan intelligent distribution system architecture

The scene of meituan's distribution business is complex , The single quantity is large . In large-scale business scenarios , Intelligent distribution becomes very important , The core of intelligent distribution is to optimize the allocation of resources .

Take out distribution business on the existing line , Also under the cable complex operation . Distribution links order demand and capacity supply . In order to achieve a balance between demand and supply , It's not just about running businesses offline 、 Operating riders , But also online supply of these needs and transport capacity to do a reasonable configuration , The aim is to improve the overall efficiency . Only to maximize the efficiency of distribution , To bring a good customer experience , Achieve lower distribution costs . The process of optimizing the allocation of resources , There are actually layers . In the understanding of meituan , It can be divided into three layers ：

1. The basic layer is structural optimization , It directly determines the upper limit of the efficiency of the distribution system . This infrastructure optimization , Long cycle , The frequency is low , Including distribution network planning 、 Capacity structure planning and so on .
2. The middle tier is market regulation , Relatively speaking, it's short to medium term , Mainly through pricing or marketing , To achieve a relatively ideal balance between supply and demand .
3. Then the upper layer is real-time matching , Do real-time resource optimal matching through scheduling . The frequency of real-time matching is the highest , The decision cycle is also the shortest .

Note:

• Base layer ： For example, adjust the transportation capacity , Long cycle , The frequency is low , There are many factors to be considered in the adjustment of transport capacity
• Middle layer ： Dynamic pricing , Marketing activities, etc , The unit volume and capacity within a certain time range can be estimated in advance , Carry out capacity scheduling or dynamic pricing in advance
• Higher level ： Real time scheduling of riders 、 Real time order allocation

As shown in the figure above , The three subsystems on the right correspond to the three-tier system , At the bottom is the planning system , The middle tier is the pricing system , The top layer is the scheduling system . Operation research optimization is a scheduling system 、 Pricing system 、 The core technology of planning system .

Note:

• Machine learning system ： for example ETA forecast
• Scheduling system ： Allocate riders according to the order
• LBS System ： Path planning
• Pricing system ： According to time 、 The weather 、 Dynamic pricing based on transportation capacity
• Planning system ： Administrative division can be used , On this basis, we will adjust

2. Practical business projects

2.1 Smart area planning

Distribution is connected to the merchant 、 customer 、 Three sides of the rider , The distribution network determines the connection among the three parties . When the user opens App, See which businesses can order , This is due to Distribution scope of merchants decision , The distribution scope of each business is different . Users order takeout at meituan , Who are the riders who serve him ？ And how to make sure ？ These are from Distribution area boundary To decide , The boundary of distribution area refers to the range corresponding to the collection of some merchants .

Note:

• merchants ： Distribution scope of merchants
• Rider ： Distribution area boundary

In traditional logistics , The most critical point affecting the efficiency of terminal distribution , It's how familiar the distributor is with his area . The more familiar , The more efficient the delivery will be . The instant delivery scenario is similar , Every rider needs to be familiar with a business or distribution area as regularly as possible . For management , The management scope of the site is also clear . If there are new businesses online , It's also easy to determine which distribution station will provide the service . therefore , There are many demands of operation management in this issue .

Problems to be solved in the regional planning project ：1. Businesses in the distribution area do not aggregate ;2. The area is strange , Empty driving is serious ;3. The size of the site is unreasonable . What is a good regional planning plan ？ Optimization goal setting based on statistical analysis .

The three elements of optimization are ： The goal is 、 constraint 、 The decision variables .

1. First of all, determine the optimization objectives . The regional planning mainly affects the riders' riding along the road 、 Deadhead rate , That is to say, the average cost of each ride paid by the rider . therefore , The business goal of the problem is to optimize the average driving distance of the rider . Based on a large number of existing regional and site accumulated data , After doing a lot of statistical analysis , You can define these indicators ： Degree of aggregation of businesses 、 The degree of aggregation of the order 、 The deviation degree between the order center of gravity and the business center of gravity . Data analysis results show that , These indexes have a strong correlation with the single average driving distance . After this layer of modeling transformation , The problem is to optimize these three indicators .
2. Sort out business constraints . There are upper limit and lower limit for single quantity in the area ; There must be no overlap between areas , There can't be businesses in more than one area ; be-all AOI(area of interest) No omission , To be covered by an area , Can't appear business does not have the service of the site ; The area boundary must be along the road network .

After the goals and constraints are set , The overall technical proposal is divided into three parts ：

1. First , According to three objective functions , Determine the best set of merchants .
2. The distribution team and the meituan map team work together . First, use the road network information , Cut the city into several non overlapping polygons , And then according to computational geometry , A group of polygons corresponding to businesses are put together to form a complete area boundary .
3. Last , Use the distribution simulation system independently developed by meituan to conduct simulation evaluation .

In the process of Regional Planning , Manual intervention is still very necessary .

2.2 Smart Rider scheduling

Take out delivery scenario orders “ Peak valley effect ” clear as daylight . The figure above is a real single curve .

The final choice of the distribution team is to arrange by group , Divide all the riders into groups , Define the start time of each group . Then you can rotate in groups , Every shift of everyone's turn will be . The algorithm should have its own optimization objective , To solve this problem , The first thing to do is design decision variables , Time is discretized , At half an hour . For a day , Only 48 Time units , There's a big reduction in decision-making space . then , The goal is to have the most time units for capacity demand to meet orders . At the modeling level , Standardized and universal models are the best choice . Meituan normalized the number of people , The algorithm assigns the proportion of riders in each shift , But regardless of the number of people . In algorithmic decision making , No decision number 、 Only the proportion of decisions , In this way, the single quantity can also be normalized . The order quantity of each time unit divided by the order quantity of peak time unit every day , Also became 0~1 Number between . If the proportion of the number of people in a certain time unit is greater than the proportion of single quantity , It is called that the transportation capacity is satisfied .

The core idea of algorithm ： Based on constraints , According to the heuristic algorithm, the initial scheme is constructed , Then local search iterative optimization .

2.3 Rider path planning

The problem of rider's path planning , It's not a simple route plan , A rider has a lot of delivery tasks , There are various constraints on these distribution tasks , How to choose the best delivery order to complete all tasks , This is a NP Difficult problem . When there is 5 Order per order 、10 At a mission point , There is a 11 More than ten thousand possible orders . System dispatch list 、 System change , All rely on path planning algorithm . At the rider's end , Recommend the order of task execution to each rider . The core demand of path planning algorithm is that the optimization effect must be stable . Can't get a good optimization result this time , It's not good next time . in addition , The running time must be short .

The stages of solving problems such as path planning ： At first , Iterative search algorithm similar to genetic algorithm , But as the volume of the business increases , It takes too long to find the algorithm , It's not acceptable at all . then , Change to a large-scale neighborhood search algorithm , But the algorithm still has strong randomness , Because without randomness, we can't get a better solution . And this search strategy based on random iteration , There's a lot of uncertainty , There will be a lot of problems in large-scale scenarios Bad Case. in addition , Iterative search takes too long . In this project , We can basically determine such a technical route . First , Only heuristic directed search can be done , We can't add random disturbance to the algorithm . The same input cannot be allowed to give different optimization results at different runtime . then , You can't search with normal iterations , We must dig out the structural characteristics of this problem , Do customized search based on knowledge .

Meituan thinks , The most important thing is the perspective on this issue . The path planning problem here , The corresponding classical problem model , It's open-loop TSP problem , Or open loop VRP A variety of ？ It can be , Or not . Meituan has made an interesting modeling transformation , Think of it as a pipeline scheduling problem ： Every order can be considered as job; The two tasks of an order are to take and deliver food , It can be thought of as a job Of operation. The passage time between any two task points , It can be thought of as sequence related preparation time . Time of delivery of each order promised , Including advance orders and instant orders , It can be mapped to the early and late penalties in pipeline scheduling problems .

Meituan adapted and improved a classical heuristic algorithm based on problem characteristics , Got very good results . Compared with the previous algorithm , Less time consuming 70%, The optimization effect is good .

2.4 Intelligent order scheduling

Distribution scheduling scenario , It can be described in mathematical language . It's not just a business issue , It is a standard combinatorial optimization problem , And it's a Markov decision process . It is not enough to make optimal allocation for a batch of orders at a certain time , You also need to consider the whole time window dimension , Every time it refers to the influence behind the party . Consider long-term optimization , Rather than a static optimization problem .

The challenge of this problem ：

1. High performance requirements , To achieve the solution of ten thousand orders to ten thousand people in seconds .
2. dynamic . As a MDP problem , Dynamic optimization scenarios need to be considered , This involves a lot of estimation . The current thinking , It is solved by other modeling transformation means .
3. There are many random factors in distribution business . For example, the delivery time of the business , Maybe it's randomness that can't be solved for a long time . Even every completed order in history , It's hard for businesses to get the real value of meal time . The merchant is uncertain about the time of meal , This random factor always exists , And very restrict the efficiency of distribution . in addition , The delivery time at the customer's location is also uncertain . The noon peak of office days , Get on the elevator 、 Time to get off the elevator , It's hard to make accurate estimates . For riders , The platform can't dictate the order in which each rider's tasks are performed . Riders are free to play in the delivery process , So there has always been uncertainty about the order in which riders perform .

Reference

1. Operational research Optimization Practice of meituan intelligent distribution system