CN115018175A - Short-term early warning evacuation path planning method based on Lagrange relaxation algorithm - Google Patents
Short-term early warning evacuation path planning method based on Lagrange relaxation algorithm Download PDFInfo
- Publication number
- CN115018175A CN115018175A CN202210700131.5A CN202210700131A CN115018175A CN 115018175 A CN115018175 A CN 115018175A CN 202210700131 A CN202210700131 A CN 202210700131A CN 115018175 A CN115018175 A CN 115018175A
- Authority
- CN
- China
- Prior art keywords
- vehicle
- node
- time
- evacuation
- new
- Prior art date
- Legal status (The legal status is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the status listed.)
- Pending
Links
- 238000000034 method Methods 0.000 title claims abstract description 41
- 230000002040 relaxant effect Effects 0.000 claims abstract description 9
- 230000009977 dual effect Effects 0.000 claims abstract description 7
- 238000010276 construction Methods 0.000 claims description 4
- 238000010586 diagram Methods 0.000 description 2
- 238000006424 Flood reaction Methods 0.000 description 1
- 238000004364 calculation method Methods 0.000 description 1
- 238000009472 formulation Methods 0.000 description 1
- 230000008014 freezing Effects 0.000 description 1
- 238000007710 freezing Methods 0.000 description 1
- 239000000446 fuel Substances 0.000 description 1
- 238000007726 management method Methods 0.000 description 1
- 239000000203 mixture Substances 0.000 description 1
- 238000012986 modification Methods 0.000 description 1
- 230000004048 modification Effects 0.000 description 1
Images
Classifications
-
- G—PHYSICS
- G06—COMPUTING; CALCULATING OR COUNTING
- G06Q—INFORMATION AND COMMUNICATION TECHNOLOGY [ICT] SPECIALLY ADAPTED FOR ADMINISTRATIVE, COMMERCIAL, FINANCIAL, MANAGERIAL OR SUPERVISORY PURPOSES; SYSTEMS OR METHODS SPECIALLY ADAPTED FOR ADMINISTRATIVE, COMMERCIAL, FINANCIAL, MANAGERIAL OR SUPERVISORY PURPOSES, NOT OTHERWISE PROVIDED FOR
- G06Q10/00—Administration; Management
- G06Q10/04—Forecasting or optimisation specially adapted for administrative or management purposes, e.g. linear programming or "cutting stock problem"
- G06Q10/047—Optimisation of routes or paths, e.g. travelling salesman problem
-
- G—PHYSICS
- G06—COMPUTING; CALCULATING OR COUNTING
- G06Q—INFORMATION AND COMMUNICATION TECHNOLOGY [ICT] SPECIALLY ADAPTED FOR ADMINISTRATIVE, COMMERCIAL, FINANCIAL, MANAGERIAL OR SUPERVISORY PURPOSES; SYSTEMS OR METHODS SPECIALLY ADAPTED FOR ADMINISTRATIVE, COMMERCIAL, FINANCIAL, MANAGERIAL OR SUPERVISORY PURPOSES, NOT OTHERWISE PROVIDED FOR
- G06Q50/00—Information and communication technology [ICT] specially adapted for implementation of business processes of specific business sectors, e.g. utilities or tourism
- G06Q50/10—Services
- G06Q50/26—Government or public services
-
- Y—GENERAL TAGGING OF NEW TECHNOLOGICAL DEVELOPMENTS; GENERAL TAGGING OF CROSS-SECTIONAL TECHNOLOGIES SPANNING OVER SEVERAL SECTIONS OF THE IPC; TECHNICAL SUBJECTS COVERED BY FORMER USPC CROSS-REFERENCE ART COLLECTIONS [XRACs] AND DIGESTS
- Y02—TECHNOLOGIES OR APPLICATIONS FOR MITIGATION OR ADAPTATION AGAINST CLIMATE CHANGE
- Y02T—CLIMATE CHANGE MITIGATION TECHNOLOGIES RELATED TO TRANSPORTATION
- Y02T10/00—Road transport of goods or passengers
- Y02T10/10—Internal combustion engine [ICE] based vehicles
- Y02T10/40—Engine management systems
Landscapes
- Business, Economics & Management (AREA)
- Human Resources & Organizations (AREA)
- Engineering & Computer Science (AREA)
- Economics (AREA)
- Strategic Management (AREA)
- Tourism & Hospitality (AREA)
- Physics & Mathematics (AREA)
- Development Economics (AREA)
- Theoretical Computer Science (AREA)
- Marketing (AREA)
- General Physics & Mathematics (AREA)
- General Business, Economics & Management (AREA)
- Game Theory and Decision Science (AREA)
- Quality & Reliability (AREA)
- Operations Research (AREA)
- Entrepreneurship & Innovation (AREA)
- Educational Administration (AREA)
- Health & Medical Sciences (AREA)
- General Health & Medical Sciences (AREA)
- Primary Health Care (AREA)
- Management, Administration, Business Operations System, And Electronic Commerce (AREA)
Abstract
The invention discloses a short-term early warning evacuation path planning method based on a Lagrange relaxation algorithm, which comprises the following steps: (1) establishing a three-dimensional vehicle/walking-time-space network according to an evacuation starting point, an evacuation destination, a departure time window and an arrival time window of the evacuated people; (2) defining a binary decision variable, and establishing a multi-passenger multi-driver network flow model; (3) and endowing the lagrangian multiplier with difficult constraint, and relaxing the lagrangian multiplier into an objective function to obtain a new lagrangian relaxation function. Solving a Lagrange dual problem with a Lagrange multiplier as a variable; (4) updating a Lagrange multiplier by using a secondary gradient method; (5) constructing a new vehicle/walking-time-space network, solving a new vehicle path problem model, and updating the search step length and the iteration times; (6) and (5) if the iteration number does not meet the requirement, iterating the steps (3) - (5) until the condition is met, and ending the loop. The invention can evacuate more people with the least cost.
Description
Technical Field
The invention belongs to the technical field of path planning, and particularly relates to a short-term early warning evacuation path planning method based on a Lagrange relaxation algorithm.
Background
Natural disasters include flood, hail, drought, typhoon, earthquake, geological disasters, low-temperature freezing, snow disasters and the like, and in recent years, economic losses caused by disasters are obviously increased. In order to reduce the direct or potential life hazards from disasters, it is necessary to evacuate the population from the disaster area to a safe place on a large scale, and such extreme events require evacuation of a large number of people from the disaster area in a short time or without prior warning. The time to prepare for predictability of a disaster occurrence directly impacts the issuance of evacuation notifications. Evacuation problems can be divided into short-term early warning evacuation and evacuation without early warning evacuation of short-term early warning disasters, and short-term early warning disasters such as typhoons or floods usually issue early warnings 24 to 72 hours ago, so that evacuation personnel and emergency management agencies are more prepared for evacuation. The lack of a private car and the lack of fuel are two major problems in emergency evacuation in the formulation of short-term early warning evacuation plans.
If passengers are allowed to walk from a starting point to an entering point or walk from a leaving point to an ending point on the basis of car sharing evacuation, the flexibility of the passengers can be fully utilized, so that the detour distance required by a driver for serving the passengers is reduced, and the evacuation time is shortened as much as possible. In actual disaster evacuation, it is difficult to determine a feasible boarding or disembarking point of a non-vehicle passenger in advance. Therefore, the research on the short-term early warning car-sharing evacuation problem allowing passengers to walk has high practical application value for successfully completing the evacuation of the short-term early warning disaster.
Disclosure of Invention
The technical problem to be solved is as follows: aiming at the problems in the prior art, the invention provides a short-term early warning evacuation path planning method based on a Lagrange relaxation algorithm, which introduces the walking of the people without vehicle evacuation into car sharing evacuation, thereby completing the evacuation of more people with the cost as low as possible.
The technical scheme is as follows:
a short-term early warning evacuation path planning method based on Lagrange relaxation algorithm is used for introducing walking information of car-free evacuation personnel into car-sharing evacuation and solving the problem of short-term early warning car-sharing evacuation under the condition that passengers are allowed to walk;
the short-term early warning evacuation path planning method comprises the following steps:
s1, adding virtual nodes and virtual road sections corresponding to the starting and ending points of all the evacuating people in the traffic network according to the evacuating starting point, the evacuating ending point, the starting time window and the arriving time window of the evacuating people and the capacity of the vehicle owned by the evacuating people with the vehicle, determining the reachable nodes of the evacuating people without the vehicle and the feasible paths of the evacuating people with the vehicle, and establishing a three-dimensional vehicle/walking-time-space network; the three-dimensional vehicle/walk-time-space network comprises a three-dimensional vehicle/walk-time-space node set, a vehicle/walk-time-space arc set connected between vehicle/walk-time-space nodes and constructed according to feasible rules, and the use cost of each vehicle/walk-time-space arc;
s2, defining binary decision variablesWherein P belongs to P, and the set P is the set of all evacuated persons; (v, u, i, j, t, s) belongs to phi, y (p, v, u, i, j, t, s) belongs to {0,1}, and phi is a feasible arc set; establishing a multi-passenger multi-driver network flow model by taking the minimum total route cost of the people evacuated without the vehicle as a target function; if y (p, v, u, i, j, t, s) is equal to 1, evacuating people p arrives at node i at time t by means of v, and arrives at node j at time s by means of u; the modes v and u include two modes of vehicle mounting and walking;
s3, endowing the lagrangian multiplier with difficult constraint, relaxing the lagrangian multiplier into an objective function to obtain a new lagrangian relaxation function, and solving a lagrangian dual problem with the lagrangian multiplier as a variable;
s4, updating the Lagrange multiplier by using a secondary gradient method;
s5, constructing a new vehicle/walking-time-space network by adopting the updated Lagrange multiplier, solving a new vehicle path problem model, and updating the search step length and the iteration times;
and S6, repeating the steps S3 to S5 until the iteration number reaches a preset iteration number threshold value, and ending the loop.
Further, in step S1, the process of adding the virtual nodes and the virtual road segments corresponding to the start and end points of all the evacuation people in the traffic network and determining the reachable nodes of the vehicle-free evacuation people and the feasible paths of the vehicle-equipped evacuation people includes the following steps:
a11, starting point o for person p to be evacuated p Adding a corresponding virtual origin o' p And road section (o) p ,o′ p ) Road section (o) p ,o′ p ) The cost is 0; destination d for evacuating person p p Adding a corresponding virtual starting point d' p And road section (d) p ,d′ p ) Road section (d) p ,d′ p ) The cost is 0;
a12, starting point o for vehicle-less evacuee pr pr If from o pr If the shortest walking distance to the actual node i in the network is less than or equal to 600 meters, the node o is connected pr And node i is added to the feasible boarding point set H of the vehicle-free evacuated persons pr pr Simultaneously adding the shortest path to the walking path set Walk of the vehicle-free evacuated person pr pr (ii) a Wherein PR belongs to PR, and the set PR is a set of all vehicle-free evacuation personnel; destination d for vehicle-free evacuated persons pr pr If from the actual nodes i to d in the network pr The shortest walking distance is less than or equal to 600 meters, the node d is connected pr And the node i is added to the feasible getting-off point set X of the vehicle-free evacuated person pr pr Simultaneously adding the shortest path to the walking path set Walk of the vehicle-free evacuated person pr pr (ii) a The shortest distance adopts the actual road network distance;
a13, for the person pd with a vehicle, calculating the starting point o from pd pd To an end point d pd Shortest path of pd Length is marked as pd Wherein PD belongs to PD, and the set PD is the set of all the persons evacuated by the train;
a14, for the vehicle-carried evacuating person pd and the vehicle-free evacuating person pr, if the actual node i ∈ H in the network pr And the actual node j in the network belongs to X pr Then calculate the pd starting point o of the person evacuating from the vehicle pd Initially, through node i and node j to end d pd The shortest path length is recorded as l pr (ii) a If l is pr ≤3×l pd Path of pd And adding the path to the feasibly path set Feasible of the vehicle evacuation people pd pd 。
Further, in step S1, the construction process of the three-dimensional vehicle/walking-time-space node set includes the following steps:
b11, virtual origin o 'for the people with evacuation pd' pd Its corresponding vehicle-space-time node is (v) pd ,o′ pd ,a pd ) Wherein v is pd Is the state of the vehicle owned by the person pd with the vehicle evacuation, a pd Is the earliest departure time of the person pd with the vehicle evacuation; virtual terminal d 'for presence evacuated people pd' pd Its corresponding vehicle-space-time node is (v) pd ,d′ pd ,b′ pd ) Wherein b' pd Is the latest arrival time of the person pd with the vehicle evacuation;
b12, virtual origin o 'for the vehicle-free evacuated person pr' pr The corresponding vehicle/walk-space-time node is (0, o' pr ,a pr ) Wherein a is pr Is the earliest departure time of the vehicle evacuation personnel pr; virtual terminal d 'for vehicle-free evacuated people pr' pr The corresponding vehicle/walk-space-time node is (0, d' pr ,b′ pr ) Wherein b' pr Is the latest arrival time of the vehicle-free evacuated person pr;
b13 for set Feasible pd Adding vehicle/walk-spatio-temporal nodes as (v) for each feasible time of each node i of each path pd I, t) where t is the vehicle v pd The time of arrival at node i;
b14 for the set Walk pr Adding vehicle/walk-spatio-temporal nodes as (w) for each feasible time of each node i of each path pr I, t) where w pr The walking state of the vehicle-free evacuee pr is shown, and t is the time when the vehicle-free evacuee pr walks to reach the node i;
b15, adding all vehicle/walking-space-time nodes obtained in the steps B11-B14 to a feasible node set omega; adding the vehicle/walk-spatio-temporal nodes obtained in the above steps B11-B12 to the virtual node set omega 0 (ii) a Adding the vehicle/walk-spatio-temporal nodes obtained in the above steps B13-B14 to the actual node set omega * 。
Further, the air conditioner is provided with a fan,in step B13, for the Feasible set pd If i is the starting point o of the evacuating people pd with a car pd Then a is pd ≤t≤b pd Wherein a is pd Is the earliest departure time of pd, b pd Is the latest departure time of pd; if i is the destination d of the people pd with the vehicle pd Then a' pd ≤t≤b′ pd Wherein a' pd Is the latest arrival time of pd, b' pd Is the latest departure time of pd; if i is not the origin o of the motorised evacuee pd pd Nor end point d pd Then a is pd ≤t≤b′ pd ;
In step B14, for the set Walk pr If i is the starting point o of the vehicle-free evacuated person pr pr Then a is a pr ≤t≤b pr Wherein a is pr Is the earliest departure time of pr, b pr Is the latest departure time of pr; if i is the destination d of the evacuated person pr without vehicle pr Then a' pr ≤t≤b′ pr . Wherein a' pr Is the latest arrival time of pr, b' pr Is the latest departure time of pr; if i is neither the starting point o of the vehicle-free evacuee pr pr Nor end point d pr Then a is pr ≤t≤b′ pr 。
Further, in step S1, the vehicle/walk-time-space arc set construction process includes the following steps:
for feasible node set omega and virtual node set omega 0 And the set of actual nodes Ω * All vehicle/pedestrian-spatio-temporal nodes in (1) were analyzed:
if (v) pd ,i,t)∈Ω * And (v) pd ,j,s)∈Ω * If a road segment from node i to node j exists in the traffic network and t (i, j) ≦ (s-t) ≦ t (i, j) +15 is satisfied, then (v) will be added pd ,v pd I, j, t, s) is added to the feasible arc set phi, wherein t (i, j) is the cost of riding through the road section (i, j);
if (w) pr ,i,t)∈Ω * And (w) pr ,j,s)∈Ω * And a link from node i to node j is in the traffic network while satisfying (s-T) ═ T (i, j), then (w) will be pr ,w pr I, j, t, s) are added to the set of feasible arcs Φ and the set of actual arcs Φ * Where T (i, j) is the cost of walking through the road segment (i, j);
if (v) pd ,i,t)∈Ω * And (w) pr ,i,s)∈Ω * If (s-t) is more than or equal to 0 and less than or equal to 15, then (v) is pd ,w pr I, j, t, s) are added to the set of feasible arcs Φ and the set of actual arcs Φ * ;
If (w) pr ,i,t)∈Ω * And (v) pd ,i,s)∈Ω * And simultaneously satisfies that (s-t) is more than or equal to 0 and less than or equal to 15, (w) is pr ,v pd I, i, s, t) is added to the set of feasible arcs Φ and the set of actual arcs Φ * ;
If (v) pd ,o′ pd ,a pd )∈Ω 0 And (v) pd ,o pd ,t)∈Ω * Then add (v) pd ,v pd ,o′ pd ,o pd ,a pd T) to a set of feasible arcs Φ and a set of virtual arcs Φ 0 ;
If (v) pd ,d′ pd ,b′ pd )∈Ω 0 And (v) pd ,d pd ,t)∈Ω * Then add (v) pd ,v pd ,d pd ,d′ pd ,t,b′ pd ) To a feasible arc set phi and a virtual arc set phi 0 ;
If (0, o' pr ,a pr )∈Ω 0 And (v) and pd ,o pr ,t)∈Ω * ,(w pr ,o pr ,t)∈Ω * then (0, v) is added pd ,o′ pr ,o pr ,a pr T) and (0, w) pr ,o′ pr ,o pr ,a pr T) to a set of feasible arcs Φ and a set of virtual arcs Φ 0 ;
If (0, d' pr ,b′ pr )∈Ω 0 And (v) and pd ,d pr ,t)∈Ω * ,(w pr ,d pr ,t)∈Ω * then add (v) pd ,0,d pr ,d′ pr ,t,b′ pr ) And (w) pr ,0,d pr ,d′ pr ,t,b′ pr ) To a feasible arc set phi and a virtual arc set phi 0 ;
For theMixing (0,0, o' pr ,d′ pr ,a pr ,b′ pr ) Adding to a feasible arc set Φ and a virtual arc set Φ 0 。
Further, the definition process of the usage cost of each vehicle/walk-time-space arc includes the following steps:
for theDefining a use cost c (v, u, i, j, t, s) of an arc (v, u, i, j, t, s) as s-t; for theIf node i is virtual origin o' p Then, the use cost c (v, u, i, j, t, s) of the arc (v, u, i, j, t, s) is defined to be 0; for theIf node j is the virtual end point d' p Then, the use cost c (v, u, i, j, t, s) of the virtual start point definition arc (v, u, i, j, t, s) is 0.
Further, in step S2, the multi-passenger multi-driver network flow model is established as follows:
initializing lambda in(v,i,t) ,λ out(v,i,t) And λ pr Are all 0, k is 0, ZR * =10000,θ 0 =1。
Further, in step S3, the difficult constraint is given to the lagrangian multiplier, a new lagrangian relaxation function is obtained by relaxing the difficult constraint into the objective function, and the process of solving the lagrangian dual problem with the lagrangian multiplier as a variable includes the following steps:
s31, introducing Lagrange multiplier lambda in the multi-passenger multi-driver network flow model established in the step S2 in(v,i,t) ,λ out(v,i,t) And λ pr And relaxing the hard constraint to a target function to obtain a new Lagrangian relaxation function as follows:
s32, establishing a new multi-passenger multi-driver network flow model as follows:
z LR =L (13);
s.t.
Further, in step S4, the process of updating the lagrangian multiplier using the secondary gradient method includes the following steps:
s41, calculating Lagrange multiplier lambda according to the following formula in(v,i,t) ,λ out(v,i,t) And λ pr The secondary gradient of (a):
s42, updating Lagrange multiplier lambda by the following formula in(v,i,t) ,λ out(v,i,t) And λ pr :
Further, in step S5, a new vehicle/pedestrian-time-space network is constructed by using the updated lagrangian multiplier, a new vehicle path problem model is solved, and the process of updating the search step length and the iteration number includes the following steps:
S51, forIf y (pd, v) pd ,v pd I, j, t, s) is 1 and (w) pr ,i,s)∈Ω * ,New_Ω * =New_Ω * ∪{(v pd ,i,t),(v pd ,j,s),(w pr ,i,s)};
For (v) pd ,i,t)∈New_Ω * ,(v pd ,j,s)∈New_Ω * If (v) pd ,v pd ,i,j,t,s)∈Ω * ,New_Φ * =New_Φ * ∪{(v pd ,v pd ,i,j,t,s)};
For (v) pd ,i,t)∈New_Ω * ,(w pr ,j,s)∈Ω * If (v) pd ,w pr ,i,j,t,s)∈Ω * ,New_Φ * =New_Φ * ∪{(v pd ,w pr ,i,j,t,s)};
For (v) pd ,i,t)∈New_Ω * ,(w pr ,j,s)∈Ω * If (w) pr ,v pd ,j,i,s,t)∈Ω * ,New_Φ * =New_Φ * ∪{(w pr ,v pd ,j,i,s,t)};
S52, establishing a new vehicle path problem as follows:
s.t.
x(pr,v,u,i,j,t,s)∈{0,1} (34);
s53, solving the vehicle path problem by using a GAMS solver to obtain a solution vectorAnd an optimum value ZR k ;
If ZR k <ZR * The optimal solution is updated according to the following formula:
ZR * =ZR k (37);
s54, mixing y * Substituting (p, v, u, i, j, t, s) into the objective function Z of the original problem to obtain a lower bound solution LB k ;
S55, updating the search step theta k And iteration number k:
k=k+1 (39)。
has the advantages that:
the short-term early warning evacuation path planning method based on the Lagrange relaxation algorithm can allow passengers to walk from a starting point to an entering point or walk from a leaving point to a destination on the basis of car sharing evacuation, and the walking of people without car evacuation is introduced into car sharing evacuation, so that the flexibility of the passengers is fully utilized, the necessary detour distance of a driver for serving the passengers is reduced, and more people are evacuated with the cost as low as possible.
Drawings
Fig. 1 is a flowchart of a short-term early warning evacuation path planning method based on a lagrangian relaxation algorithm according to an embodiment of the present invention;
FIG. 2 is a three-dimensional vehicle/walk-time-space network architecture diagram of an embodiment of the present invention;
FIG. 3 is a time-space diagram of the solution result according to the embodiment of the present invention.
Detailed Description
The following examples are presented to enable one of ordinary skill in the art to more fully understand the present invention and are not intended to limit the invention in any way.
Fig. 1 is a flowchart of a short-term early warning evacuation path planning method based on a lagrangian relaxation algorithm according to an embodiment of the present invention. Referring to fig. 1, the short-term early warning evacuation path planning method is used for introducing walking information of people without car evacuation into car-sharing evacuation, and solving the problem of short-term early warning car-sharing evacuation when passengers are allowed to walk;
the short-term early warning evacuation path planning method comprises the following steps:
s1, adding virtual nodes and virtual road sections corresponding to the start and end points of all the evacuation persons in the traffic network according to the evacuation start point, the evacuation end point, the start time window and the arrival time window of the evacuation persons and the capacity of the vehicles owned by the evacuation persons with the vehicles, determining the reachable nodes of the evacuation persons without the vehicles and the feasible paths of the evacuation persons with the vehicles, and establishing a three-dimensional vehicle/walking-time-space network; the three-dimensional vehicle/walk-time-space network includes a set of three-dimensional vehicle/walk-time-space nodes, a set of vehicle/walk-time-space arcs connecting between the vehicle/walk-time-space nodes constructed according to feasible rules, and a cost of use for each vehicle/walk-time-space arc.
S2, defining binary decision variablesWherein P belongs to P, and the set P is the set of all evacuated persons; (v, u, i, j, t, s) belongs to phi, y (p, v, u, i, j, t, s) belongs to {0,1}, and phi is a feasible arc set; and establishing a multi-passenger multi-driver network flow model by taking the minimization of the total route cost of the people evacuated without the vehicle as an objective function. If y (p, v, u, i, j, t, s) is equal to 1, the evacuee p can arrive at node j at time s in a vehicle/walking manner v from node i at time t in a vehicle/walking manner u.
And S3, endowing the lagrangian multiplier with difficult constraint, relaxing the lagrangian multiplier into an objective function to obtain a new lagrangian relaxation function, and solving a lagrangian dual problem with the lagrangian multiplier as a variable.
And S4, updating the Lagrangian multiplier by using a secondary gradient method.
And S5, constructing a new vehicle/walking-time-space network by adopting the updated Lagrange multiplier, solving a new vehicle path problem model, and updating the search step length and the iteration times.
And S6, repeating the steps S3 to S5 until the iteration number reaches a preset iteration number threshold value, and ending the loop.
(1) And establishing a three-dimensional vehicle/walking-time-space network according to the evacuation starting point, the evacuation destination, the departure time window and the arrival time window of the evacuated people. Table 1 shows the evacuated person information of the present example. In this example, the detour tolerance of the vehicle is set to 0, and thus the traveling path of the vehicle is the shortest path of the vehicle, i.e., 1-2-4-5-8. Meanwhile, the vehicle capacity is set to be 3, the maximum walking distance is set to be 3, the feasible boarding point set of the people to be evacuated without the vehicle 1 is {2,4}, and the feasible disembarking point set is {5,6 }; the feasible boarding point set of the vehicle-free evacuated personnel 2 is {3,4}, and the feasible disembarking point set is {4,5 }.
Table 1 evacuation personnel information table of this example
(2) Defining binary decision variables the binary decision variables are defined:
and establishing a multi-passenger multi-driver network flow model. The model objective function is to minimize the total route cost, and the constraint conditions include a start point flow balance constraint, a finish point flow balance constraint, an intermediate node flow balance constraint, a vehicle capacity constraint and a vehicle usage constraint for each evacuated person.
(3) Assigning a vehicle capacity constraint and a vehicle usage constraint to lagrange multipliers λ, respectively in(v,i,t) ,λ out(v,i,t) And λ pr And relaxing the Lagrange function L into the target function to obtain a new Lagrange relaxation function L, and solving a Lagrange dual problem with a Lagrange multiplier as a variable. The objective function of the problem is L, and the constraints comprise a starting point flow balance constraint, a finishing point flow balance constraint and an intermediate node flow balance constraint of each evacuation person:
(4) computing lagrange multiplier λ in(v,i,t) ,λ out(v,i,t) And λ pr The secondary gradient of (a):
updating lagrange multiplier lambda in(v,i,t) ,λ out(v,i,t) And λ pr The calculation formula is as follows:
(5) constructing a new vehicle/walking-time-space network based on the result solved in the step (3), and solving a new vehicle path problem model with the model variables ofThe objective function is to minimize the total route cost of the vehicle-free evacuated persons, and the constraint conditions comprise a starting point flow balance constraint, a finishing point flow balance constraint, an intermediate node flow balance constraint, a vehicle capacity constraint and a vehicle use constraint of each vehicle-free evacuated person. And updating the search step length and the iteration times:
k=k+1。
(6) and (5) if the iteration times do not meet the requirements, iterating the steps (3) to (5) until the conditions are met, and ending the loop.
The above description is for the purpose of describing the invention in more detail with reference to specific preferred embodiments, and it should not be construed that the embodiments are limited to those described herein, but rather that the invention is susceptible to various modifications and alternative forms without departing from the spirit and scope of the present invention.
Claims (10)
1. A short-term early warning evacuation path planning method based on a Lagrange relaxation algorithm is characterized in that the short-term early warning evacuation path planning method is used for introducing walking information of people without car evacuation into car sharing evacuation and solving the problem of short-term early warning car sharing evacuation under the condition that passengers are allowed to walk;
the short-term early warning evacuation path planning method comprises the following steps:
s1, adding virtual nodes and virtual road sections corresponding to the start and end points of all the evacuation persons in the traffic network according to the evacuation start point, the evacuation end point, the start time window and the arrival time window of the evacuation persons and the capacity of the vehicles owned by the evacuation persons with the vehicles, determining the reachable nodes of the evacuation persons without the vehicles and the feasible paths of the evacuation persons with the vehicles, and establishing a three-dimensional vehicle/walking-time-space network; the three-dimensional vehicle/walk-time-space network comprises a three-dimensional vehicle/walk-time-space node set, a vehicle/walk-time-space arc set connected between vehicle/walk-time-space nodes and constructed according to feasible rules, and the use cost of each vehicle/walk-time-space arc;
s2, defining binary decision variablesWherein P belongs to P, and the set P is the set of all evacuated persons; (v, u, i, j, t, s) belongs to phi, y (p, v, u, i, j, t, s) belongs to {0,1}, and phi is a feasible arc set; establishing a multi-passenger multi-driver network flow model by taking the minimum total route cost of the people evacuated without the vehicle as a target function; if y (p, v, u, i, j, t, s) is equal to 1, evacuating people p arrives at node i at time t by means of v, and arrives at node j at time s by means of u; the modes v and u include two modes of vehicle mounting and walking;
s3, endowing the lagrangian multiplier with difficult constraint, relaxing the lagrangian multiplier into an objective function to obtain a new lagrangian relaxation function, and solving a lagrangian dual problem with the lagrangian multiplier as a variable;
s4, updating the Lagrange multiplier by using a secondary gradient method;
s5, constructing a new vehicle/walking-time-space network by adopting the updated Lagrange multiplier, solving a new vehicle path problem model, and updating the search step length and the iteration times;
and S6, repeating the steps S3 to S5 until the iteration number reaches a preset iteration number threshold value, and ending the loop.
2. The method for planning a short-term early warning evacuation path based on the Lagrange relaxation algorithm as claimed in claim 1, wherein in step S1, adding virtual nodes and virtual road segments corresponding to the start and end points of all the evacuated persons in the traffic network, and determining the reachable nodes of the evacuated persons without vehicles and the feasible paths of the evacuated persons with vehicles comprises the following steps:
a11, starting point o for person p to be evacuated p Adding a corresponding virtual origin o' p And road section (o) p ,o′ p ) Road section (o) p ,o′ p ) The cost is 0; destination d for evacuating person p p Adding a corresponding virtual starting point d' p And road section (d) p ,d′ p ) Road section (d) p ,d′ p ) The cost is 0;
a12, starting point o for the vehicle-less evacuated person pr pr If from o pr Shortest walking distance to actual node i in the network is less than or equal toAt 600 m, the node o is connected pr And node i is added to the feasible boarding point set H of the vehicle-free evacuated persons pr pr Simultaneously adding the shortest path to the walking path set Walk of the vehicle-free evacuated person pr pr (ii) a Wherein PR belongs to PR, and the set PR is a set of all vehicle-free evacuation personnel; destination d for vehicle-free evacuated persons pr pr If from the actual nodes i to d in the network pr The shortest walking distance is less than or equal to 600 meters, the node d is connected pr And the node i is added to the feasible getting-off point set X of the vehicle-free evacuated person pr pr Simultaneously adding the shortest path to the walking path set Walk of the vehicle-free evacuated person pr pr (ii) a The shortest distance adopts the actual road network distance;
a13, for the person pd with a vehicle, calculating the starting point o from pd pd To an end point d pd Shortest path of pd Length is marked as pd Wherein PD belongs to PD, and the set PD is the set of all the persons evacuated by the train;
a14, for the vehicle-carried evacuating person pd and the vehicle-free evacuating person pr, if the actual node i ∈ H in the network pr And the actual node j in the network belongs to X pr Then calculate the pd starting point o of the person evacuating from the vehicle pd Initially, through node i and node j to end d pd The shortest path length is recorded as l pr (ii) a If l is pr ≤3×l pd Path of pd And adding the path to the feasibly path set Feasible of the vehicle evacuation people pd pd 。
3. The method for planning a short-term early warning evacuation path based on the lagrangian relaxation algorithm as claimed in claim 1, wherein in step S1, the construction process of the three-dimensional vehicle/walk-time-space node set comprises the following steps:
b11, virtual origin o 'for the people with evacuation pd' pd Its corresponding vehicle-space-time node is (v) pd ,o′ pd ,a pd ) Wherein v is pd Is the state of the vehicle owned by the person pd with the vehicle evacuation, a pd Is the earliest departure time of the person pd having a vehicle to be evacuatedA (c) is added; virtual terminal d 'for presence evacuated people pd' pd Its corresponding vehicle-space-time node is (v) pd ,d′ pd ,b′ pd ) Wherein b' pd Is the latest arrival time of the person pd with the vehicle evacuation;
b12, virtual origin o 'for the vehicle-free evacuated person pr' pr The corresponding vehicle/walk-space-time node is (0, o' pr ,a pr ) Wherein a is pr Is the earliest departure time of the vehicle evacuating personnel pr; virtual terminal d 'for vehicle-free evacuated people pr' pr The corresponding vehicle/walk-space-time node is (0, d' pr ,b′ pr ) Wherein b' pr Is the latest arrival time of the vehicle-free evacuated person pr;
b13 for set Feasible pd Adding vehicle/walk-spatio-temporal nodes as (v) for each feasible time of each node i of each path pd I, t) where t is the vehicle v pd The time of arrival at node i;
b14 for the set Walk pr Adding vehicle/walk-spatio-temporal nodes as (w) for each feasible time of each node i of each path pr I, t) where w pr The walking state of the vehicle-free evacuee pr is shown, and t is the time when the vehicle-free evacuee pr walks to reach the node i;
b15, adding all vehicle/walking-space-time nodes obtained in the steps B11-B14 to a feasible node set omega; adding the vehicle/walk-spatio-temporal nodes obtained in the above steps B11-B12 to the virtual node set omega 0 (ii) a Adding the vehicle/walk-spatio-temporal nodes obtained in the above steps B13-B14 to the actual node set omega * 。
4. The method for planning a short-term early warning evacuation path based on the Lagrangian relaxation algorithm as claimed in claim 3, wherein in the step B13, for the Feasible set pd If i is the starting point o of the evacuating person pd with vehicle pd Then a is pd ≤t≤b pd Wherein a is pd Is the earliest departure time of pd, b pd Is the latest out of pdSending time; if i is the destination d of the person pd with the vehicle pd Then a' pd ≤t≤b′ pd Wherein a' pd Is the latest arrival time of pd, b' pd Is the latest departure time of pd; if i is not the origin o of the motorised evacuee pd pd Nor end point d pd Then a is pd ≤t≤b′ pd ;
In step B14, for the set Walk pr If i is the starting point o of the vehicle-free evacuated person pr pr Then a is pr ≤t≤b pr Wherein a is pr Is the earliest departure time of pr, b pr Is the latest departure time of pr; if i is the destination d of the evacuated person pr without vehicle pr Then a' pr ≤t≤b′ pr . Wherein a' pr Is the latest arrival time of pr, b' pr Is the latest departure time of pr; if i is neither the starting point o of the vehicle-free evacuee pr pr Nor end point d pr Then a is pr ≤t≤b′ pr 。
5. The method for planning a short-term early warning evacuation path based on the Lagrangian relaxation algorithm as claimed in claim 3, wherein the vehicle/walk-time-space arc set construction process in step S1 comprises the following steps:
for feasible node set omega and virtual node set omega 0 And the set of actual nodes Ω * All vehicle/pedestrian-spatio-temporal nodes in (1) were analyzed:
if (v) pd ,i,t)∈Ω * And (v) pd ,j,s)∈Ω * If a road segment from node i to node j exists in the traffic network and t (i, j) ≦ (s-t) ≦ t (i, j) +15 is satisfied, then (v) will be added pd ,v pd I, j, t, s) is added to the feasible arc set Φ, where t (i, j) is the cost of the ride through the road segment (i, j);
if (w) pr ,i,t)∈Ω * And (w) pr ,j,s)∈Ω * And the section from the node i to the node j is in the traffic network and simultaneously satisfies(s-T) ═ T (i, j), then (w) pr ,w pr I, j, t, s) are added to the set of feasible arcs Φ and the set of actual arcs Φ * Where T (i, j) is the cost of walking through the road segment (i, j);
if (v) pd ,i,t)∈Ω * And (w) pr ,i,s)∈Ω * If (s-t) is more than or equal to 0 and less than or equal to 15, then (v) is pd ,w pr I, j, t, s) are added to the set of feasible arcs Φ and the set of actual arcs Φ * ;
If (w) pr ,i,t)∈Ω * And (v) pd ,i,s)∈Ω * And simultaneously satisfies that (s-t) is more than or equal to 0 and less than or equal to 15, (w) is pr ,v pd I, i, s, t) is added to the set of feasible arcs Φ and the set of actual arcs Φ * ;
If (v) pd ,o′ pd ,a pd )∈Ω 0 And (v) pd ,o pd ,t)∈Ω * Then add (v) pd ,v pd ,o′ pd ,o pd ,a pd T) to a set of feasible arcs Φ and a set of virtual arcs Φ 0 ;
If (v) pd ,d′ pd ,b′ pd )∈Ω 0 And (v) pd ,d pd ,t)∈Ω * Then add (v) pd ,v pd ,d pd ,d′ pd ,t,b′ pd ) To a feasible arc set phi and a virtual arc set phi 0 ;
If (0, o' pr ,a pr )∈Ω 0 And (v) and pd ,o pr ,t)∈Ω * ,(w pr ,o pr ,t)∈Ω * then (0, v) is added pd ,o′ pr ,o pr ,a pr T) and (0, w) pr ,o′ pr ,o pr ,a pr T) to a set of feasible arcs Φ and a set of virtual arcs Φ 0 ;
If (0, d' pr ,b′ pr )∈Ω 0 And (v) and pd ,d pr ,t)∈Ω * ,(w pr ,d pr ,t)∈Ω * then add (v) pd ,0,d pr ,d′ pr ,t,b′ pr ) And (w) pr ,0,d pr ,d′ pr ,t,b′ pr ) To a feasible arc set phi and a virtual arc set phi 0 ;
6. The method of short-term early warning evacuation path planning based on lagrangian relaxation algorithm as claimed in claim 5, wherein the process of defining the cost of use for each vehicle/pedestrian-time-space arc comprises the steps of:
for theDefining a use cost c (v, u, i, j, t, s) of an arc (v, u, i, j, t, s) as s-t; for theIf node i is virtual origin o' p Then, the use cost c (v, u, i, j, t, s) of the arc (v, u, i, j, t, s) is defined to be 0; for theIf node j is virtual terminal d' p Then, the virtual starting point defines the use cost c (v, u, i, j, t, s) of the arc (v, u, i, j, t, s) to be 0.
7. The lagrangian relaxation algorithm-based short-term early warning evacuation path planning method according to claim 1, wherein in step S2, the established multi-passenger multi-driver network flow model is:
initializing lambda in(v,i,t) ,λ out(v,i,t) And λ pr Are all 0, k is 0, ZR * =10000,θ 0 =1。
8. The method for planning a short-term early warning evacuation path based on the lagrangian relaxation algorithm as claimed in claim 7, wherein in step S3, the lagrangian multiplier is given with the hard constraint, a new lagrangian relaxation function is obtained by relaxing into the objective function, and the process of solving the lagrangian dual problem with the lagrangian multiplier as a variable includes the following steps:
s31, introducing Lagrange multiplier lambda in the multi-passenger multi-driver network flow model established in the step S2 in(v,i,t) ,λ out(v,i,t) And λ pr And relaxing the hard constraint to a target function to obtain a new Lagrangian relaxation function as follows:
s32, establishing a new multi-passenger multi-driver network flow model as follows:
z LR =L (13);
s.t.
9. The method for planning a short-term early warning evacuation path based on the lagrangian relaxation algorithm as claimed in claim 8, wherein the step S4, updating the lagrangian multiplier using the secondary gradient method comprises the following steps:
s41, calculating Lagrange multiplier lambda according to the following formula in(v,i,t) ,λ out(v,i,t) And λ pr The secondary gradient of (a):
s42, updating Lagrange multiplier lambda by the following formula in(v,i,t) ,λ out(v,i,t) And λ pr :
10. The method of short-term early warning evacuation path planning based on lagrangian relaxation algorithm as claimed in claim 8, wherein step S5 is performed by constructing a new vehicle/pedestrian-time-space network using the updated lagrangian multiplier, solving a new vehicle path problem model, and updating the search step size and the number of iterations simultaneously comprises the following steps:
s51, creating new vehicle/walk-spatio-temporal node setNew vehicle/pedestrian-spatiotemporal arc set
S51, forIf y (pd, v) pd ,v pd I, j, t, s) is 1 and (w) pr ,i,s)∈Ω * ,New_Ω * =New_Ω * ∪{(v pd ,i,t),(v pd ,j,s),(w pr ,i,s)};
For (v) pd ,i,t)∈New_Ω * ,(v pd ,j,s)∈New_Ω * If (v) pd ,v pd ,i,j,t,s)∈Ω * ,New_Φ * =New_Φ * ∪{(v pd ,v pd ,i,j,t,s)};
For (v) pd ,i,t)∈New_Ω * ,(w pr ,j,s)∈Ω * If (v) pd ,w pr ,i,j,t,s)∈Ω * ,New_Φ * =New_Φ * ∪{(v pd ,w pr ,i,j,t,s)};
For (v) pd ,i,t)∈New_Ω * ,(w pr ,j,s)∈Ω * If (w) pr ,v pd ,j,i,s,t)∈Ω * ,New_Φ * =New_Φ * ∪{(w pr ,v pd ,j,i,s,t)};
S52, establishing a new vehicle path problem as follows:
s.t.
x(pr,v,u,i,j,t,s)∈{0,1} (34);
s53, solving the vehicle path problem by using a GAMS solver to obtain a solution vectorAnd an optimum value ZR k ;
If ZR k <ZR * The optimal solution is updated according to the following formula:
ZR * =ZR k (37);
s54, mixing y * Substituting (p, v, u, i, j, t, s) into the objective function Z of the original problem to obtain a lower bound solution LB k ;
S55, updating the search step theta k And iteration number k:
k=k+1 (39)。
Priority Applications (1)
Application Number | Priority Date | Filing Date | Title |
---|---|---|---|
CN202210700131.5A CN115018175A (en) | 2022-06-20 | 2022-06-20 | Short-term early warning evacuation path planning method based on Lagrange relaxation algorithm |
Applications Claiming Priority (1)
Application Number | Priority Date | Filing Date | Title |
---|---|---|---|
CN202210700131.5A CN115018175A (en) | 2022-06-20 | 2022-06-20 | Short-term early warning evacuation path planning method based on Lagrange relaxation algorithm |
Publications (1)
Publication Number | Publication Date |
---|---|
CN115018175A true CN115018175A (en) | 2022-09-06 |
Family
ID=83076834
Family Applications (1)
Application Number | Title | Priority Date | Filing Date |
---|---|---|---|
CN202210700131.5A Pending CN115018175A (en) | 2022-06-20 | 2022-06-20 | Short-term early warning evacuation path planning method based on Lagrange relaxation algorithm |
Country Status (1)
Country | Link |
---|---|
CN (1) | CN115018175A (en) |
Cited By (1)
Publication number | Priority date | Publication date | Assignee | Title |
---|---|---|---|---|
CN118247111A (en) * | 2024-04-15 | 2024-06-25 | 长安大学 | Double-layer vehicle path planning method based on Lagrange relaxation algorithm |
Citations (4)
Publication number | Priority date | Publication date | Assignee | Title |
---|---|---|---|---|
WO2006113598A2 (en) * | 2005-04-15 | 2006-10-26 | Otis Elevator Company | Group elevator scheduling with advanced traffic information |
CN107341580A (en) * | 2017-08-08 | 2017-11-10 | 上海交通大学 | A kind of new heuritic approach for the planning of urban traffic network emergency evacuation |
CN111860991A (en) * | 2020-07-13 | 2020-10-30 | 清华大学深圳国际研究生院 | Unmanned vehicle distribution path planning method |
US20220137961A1 (en) * | 2020-11-05 | 2022-05-05 | Mitsubishi Electric Research Laboratories, Inc. | Controller with Early Termination in Mixed-Integer Optimal Control Optimization |
-
2022
- 2022-06-20 CN CN202210700131.5A patent/CN115018175A/en active Pending
Patent Citations (4)
Publication number | Priority date | Publication date | Assignee | Title |
---|---|---|---|---|
WO2006113598A2 (en) * | 2005-04-15 | 2006-10-26 | Otis Elevator Company | Group elevator scheduling with advanced traffic information |
CN107341580A (en) * | 2017-08-08 | 2017-11-10 | 上海交通大学 | A kind of new heuritic approach for the planning of urban traffic network emergency evacuation |
CN111860991A (en) * | 2020-07-13 | 2020-10-30 | 清华大学深圳国际研究生院 | Unmanned vehicle distribution path planning method |
US20220137961A1 (en) * | 2020-11-05 | 2022-05-05 | Mitsubishi Electric Research Laboratories, Inc. | Controller with Early Termination in Mixed-Integer Optimal Control Optimization |
Cited By (2)
Publication number | Priority date | Publication date | Assignee | Title |
---|---|---|---|---|
CN118247111A (en) * | 2024-04-15 | 2024-06-25 | 长安大学 | Double-layer vehicle path planning method based on Lagrange relaxation algorithm |
CN118247111B (en) * | 2024-04-15 | 2024-10-11 | 长安大学 | Double-layer vehicle path planning method based on Lagrange relaxation algorithm |
Similar Documents
Publication | Publication Date | Title |
---|---|---|
US9308827B2 (en) | Reachable range calculation apparatus, method, and program | |
CN107103142A (en) | Comprehensive traffic network operation situation towards highway and the railway network deduces emulation technology | |
CN107194128A (en) | Multi-mode public transport network design method based on center radial pattern network frame | |
CN110599760B (en) | Travel behavior simulation method under multi-mode traffic network | |
CN109543934A (en) | The evaluation method of the overall target of urban public traffic network | |
CN115527369B (en) | Large passenger flow early warning and evacuation method under large-area delay condition of airport hub | |
CN107516147A (en) | A kind of high-speed railway line train starting scheme optimization method and its system | |
CN115018175A (en) | Short-term early warning evacuation path planning method based on Lagrange relaxation algorithm | |
Xiaoxue | Optimal route planning of parking lot based on Dijkstra algorithm | |
CN111724076A (en) | Regional multi-type rail transit passenger flow dynamic distribution method under operation interruption condition | |
Milan | Multicriteria evaluation of the high speed rail, transrapid maglev and hyperloop systems | |
Yu et al. | Advanced multi-modal routing approach for pedestrians | |
CN114048917A (en) | Crowd evacuation path recommendation method and system based on position | |
CN111680822B (en) | Reciprocating type bus evacuation path planning method based on non-fixed route | |
CN110895749B (en) | Positioning-path planning method for emergency logistics | |
CN106067078A (en) | Bus berth distribution optimization method for double platforms | |
Verbas et al. | Finding least cost hyperpaths in multimodal transit networks: Methodology, algorithm, and large-scale application | |
JP2019211279A (en) | Rideshare information processing program and rideshare information processing device | |
Wan et al. | Congested multimodal transit network design | |
Rodriguez-Vega et al. | A graph-based mobility model for electric vehicles in urban traffic networks: Application to the grenoble metropolitan area | |
CN113657672B (en) | Comprehensive terminal bus linking method based on dynamic programming | |
CN114264313B (en) | Potential energy-based lane-level path planning method, system, equipment and storage medium | |
Moon et al. | Energy-Efficient Routing of a Heterogeneous Vehicle Fleet with Optimized Speed Profiling | |
Czioska et al. | Determination of efficient meeting points in ride-sharing scenarios | |
CN112781610A (en) | Unmanned bus route planning method in multi-passenger mode |
Legal Events
Date | Code | Title | Description |
---|---|---|---|
PB01 | Publication | ||
PB01 | Publication | ||
SE01 | Entry into force of request for substantive examination | ||
SE01 | Entry into force of request for substantive examination |