[go: up one dir, main page]
More Web Proxy on the site http://driver.im/

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 PDF

Info

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
Application number
CN202210700131.5A
Other languages
Chinese (zh)
Inventor
程琳
夏益翀
Current Assignee (The listed assignees may be inaccurate. Google has not performed a legal analysis and makes no representation or warranty as to the accuracy of the list.)
Southeast University
Original Assignee
Southeast University
Priority date (The priority date 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 date listed.)
Filing date
Publication date
Application filed by Southeast University filed Critical Southeast University
Priority to CN202210700131.5A priority Critical patent/CN115018175A/en
Publication of CN115018175A publication Critical patent/CN115018175A/en
Pending legal-status Critical Current

Links

Images

Classifications

    • GPHYSICS
    • G06COMPUTING; CALCULATING OR COUNTING
    • G06QINFORMATION 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/00Administration; Management
    • G06Q10/04Forecasting or optimisation specially adapted for administrative or management purposes, e.g. linear programming or "cutting stock problem"
    • G06Q10/047Optimisation of routes or paths, e.g. travelling salesman problem
    • GPHYSICS
    • G06COMPUTING; CALCULATING OR COUNTING
    • G06QINFORMATION 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/00Information and communication technology [ICT] specially adapted for implementation of business processes of specific business sectors, e.g. utilities or tourism
    • G06Q50/10Services
    • G06Q50/26Government or public services
    • YGENERAL 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
    • Y02TECHNOLOGIES OR APPLICATIONS FOR MITIGATION OR ADAPTATION AGAINST CLIMATE CHANGE
    • Y02TCLIMATE CHANGE MITIGATION TECHNOLOGIES RELATED TO TRANSPORTATION
    • Y02T10/00Road transport of goods or passengers
    • Y02T10/10Internal combustion engine [ICE] based vehicles
    • Y02T10/40Engine 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

Short-term early warning evacuation path planning method based on Lagrange relaxation algorithm
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 variables
Figure BDA0003703672600000021
Wherein 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 the
Figure BDA00037036726000000512
Mixing (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 the
Figure BDA0003703672600000051
Defining a use cost c (v, u, i, j, t, s) of an arc (v, u, i, j, t, s) as s-t; for the
Figure BDA0003703672600000052
If 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 the
Figure BDA0003703672600000053
If 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:
Figure BDA0003703672600000054
Figure BDA0003703672600000055
Figure BDA0003703672600000056
Figure BDA0003703672600000057
Figure BDA0003703672600000058
Figure BDA0003703672600000059
Figure BDA00037036726000000510
Figure BDA00037036726000000511
Figure BDA0003703672600000061
Figure BDA0003703672600000062
Figure BDA0003703672600000063
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:
Figure BDA0003703672600000064
s32, establishing a new multi-passenger multi-driver network flow model as follows:
z LR =L (13);
s.t.
Figure BDA0003703672600000065
Figure BDA0003703672600000066
Figure BDA0003703672600000067
Figure BDA0003703672600000071
Figure BDA0003703672600000072
Figure BDA0003703672600000073
Figure BDA0003703672600000074
s33, makingSolving the model in the step S32 by using a GAMS solver to obtain a solution vector set
Figure BDA0003703672600000075
Figure BDA0003703672600000076
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):
Figure BDA0003703672600000077
Figure BDA0003703672600000078
Figure BDA0003703672600000079
s42, updating Lagrange multiplier lambda by the following formula in(v,i,t) ,λ out(v,i,t) And λ pr
Figure BDA00037036726000000710
Figure BDA00037036726000000711
Figure BDA00037036726000000712
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, creating new vehicle/walking-space-time node set
Figure BDA00037036726000000713
New vehicle/pedestrian-spatiotemporal arc set
Figure BDA0003703672600000081
S51, for
Figure BDA0003703672600000082
If 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:
Figure BDA0003703672600000083
s.t.
Figure BDA0003703672600000084
Figure BDA0003703672600000085
Figure BDA0003703672600000086
Figure BDA0003703672600000087
Figure BDA0003703672600000088
Figure BDA0003703672600000089
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 vector
Figure BDA0003703672600000091
And an optimum value ZR k
If ZR k <ZR * The optimal solution is updated according to the following formula:
Figure BDA0003703672600000092
Figure BDA0003703672600000093
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:
Figure BDA0003703672600000094
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 variables
Figure BDA0003703672600000101
Wherein 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
Figure BDA0003703672600000102
(2) Defining binary decision variables the binary decision variables are defined:
Figure BDA0003703672600000103
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:
Figure BDA0003703672600000111
(4) computing lagrange multiplier λ in(v,i,t) ,λ out(v,i,t) And λ pr The secondary gradient of (a):
Figure BDA0003703672600000112
Figure BDA0003703672600000113
Figure BDA0003703672600000114
updating lagrange multiplier lambda in(v,i,t) ,λ out(v,i,t) And λ pr The calculation formula is as follows:
Figure BDA0003703672600000115
Figure BDA0003703672600000116
Figure BDA0003703672600000117
(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 of
Figure BDA0003703672600000118
The 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:
Figure BDA0003703672600000121
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 variables
Figure FDA0003703672590000011
Wherein 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
For the
Figure FDA0003703672590000041
Mixing (0,0, o' pr ,d′ pr ,a pr ,b′ pr ) Adding to a feasible arc set Φ and a virtual arc set Φ 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 the
Figure FDA0003703672590000042
Defining a use cost c (v, u, i, j, t, s) of an arc (v, u, i, j, t, s) as s-t; for the
Figure FDA0003703672590000043
If 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 the
Figure FDA0003703672590000044
If 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:
Figure FDA0003703672590000045
Figure FDA0003703672590000046
Figure FDA0003703672590000047
Figure FDA0003703672590000051
Figure FDA0003703672590000052
Figure FDA0003703672590000053
Figure FDA0003703672590000054
Figure FDA0003703672590000055
Figure FDA0003703672590000056
Figure FDA0003703672590000057
Figure FDA0003703672590000058
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:
Figure FDA0003703672590000061
s32, establishing a new multi-passenger multi-driver network flow model as follows:
z LR =L (13);
s.t.
Figure FDA0003703672590000062
Figure FDA0003703672590000063
Figure FDA0003703672590000064
Figure FDA0003703672590000065
Figure FDA0003703672590000066
Figure FDA0003703672590000067
Figure FDA0003703672590000068
s33, solving the model in the step S32 by using a GAMS solver to obtain a solution vector set
Figure FDA0003703672590000069
Figure FDA00037036725900000610
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):
Figure FDA0003703672590000071
Figure FDA0003703672590000072
Figure FDA0003703672590000073
s42, updating Lagrange multiplier lambda by the following formula in(v,i,t) ,λ out(v,i,t) And λ pr
Figure FDA0003703672590000074
Figure FDA0003703672590000075
Figure FDA0003703672590000076
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 set
Figure FDA0003703672590000077
New vehicle/pedestrian-spatiotemporal arc set
Figure FDA0003703672590000078
S51, for
Figure FDA0003703672590000079
If 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:
Figure FDA0003703672590000081
s.t.
Figure FDA0003703672590000082
Figure FDA0003703672590000083
Figure FDA0003703672590000084
Figure FDA0003703672590000085
Figure FDA0003703672590000086
Figure FDA0003703672590000087
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 vector
Figure FDA0003703672590000088
And an optimum value ZR k
If ZR k <ZR * The optimal solution is updated according to the following formula:
Figure FDA0003703672590000089
Figure FDA00037036725900000810
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:
Figure FDA00037036725900000811
k=k+1 (39)。
CN202210700131.5A 2022-06-20 2022-06-20 Short-term early warning evacuation path planning method based on Lagrange relaxation algorithm Pending CN115018175A (en)

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)

* Cited by examiner, † Cited by third party
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)

* Cited by examiner, † Cited by third party
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

Patent Citations (4)

* Cited by examiner, † Cited by third party
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)

* Cited by examiner, † Cited by third party
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