CN117132011A - Intercity travel vehicle route determination method, system, electronic device and medium - Google Patents

Abstract

The invention discloses a method, a system, electronic equipment and a medium for determining an inter-city travel vehicle path, which relate to the fields of intelligent optimization algorithms and vehicle scheduling, wherein the method for determining the path comprises the following steps: constructing an inter-city travel vehicle path model by taking the maximized average number of passengers per trip, the minimized number of vehicles, the minimized total travel distance of the vehicles and the minimized total waiting time of the passengers as objective functions and taking the vehicle passenger capacity, the service quality, the time constraint and the safety constraint as constraint conditions; acquiring an inter-city order to be travelled; and determining the travel vehicles corresponding to each travel order according to the inter-city travel vehicle path model. The invention can provide a path planning scheme for meeting a plurality of requirements for the travel of the inter-city network about vehicles.

Description

Method, system, electronic device and medium for determining intercity travel vehicle path

Technical Field

The present invention relates to the field of intelligent optimization algorithms and vehicle scheduling, and in particular to a method, system, electronic equipment and medium for determining a vehicle path for inter-city travel.

Background Art

With the popularity of smartphones and applications, more and more companies are developing ride-sharing platforms consisting of professional drivers and commercial vehicles. Based on Internet technology, they integrate supply and demand information, reasonably match passengers and drivers, and plan travel routes efficiently and safely to realize commercial activities of non-traditional taxi booking services. This new mobile service has experienced rapid growth and has grown exponentially to provide services to most metropolitan areas across 66 countries. Due to these advantages, online ride-hailing has quickly become popular in China. Intercity travel can make full use of vehicle vacancy resources to meet the travel needs of car-free users, avoid congestion, and save travel time. At the same time, it reduces the vehicle travel costs of private car owners, improves vehicle utilization, alleviates traffic congestion, saves resources, and protects the environment. Therefore, intercity travel has important practical significance.

However, few people have studied the vehicle routing problem for intercity travel. At present, the application scenarios of carpooling are mostly carpooling travel within the city. Intracity travel has four characteristics: high travel demand, high travel frequency, short travel distance, and convenient travel. These characteristics make intracity travel usually carried out in real time. In order to ensure the quality of service, the platform needs to respond to passengers' requests in a very short time. Unlike intracity travel, intercity travel has the following characteristics: low travel demand, low travel frequency, long travel distance, and few travel options. These characteristics make intercity travel usually highly planned, especially non-self-driving travel. Since intercity travel is a long-distance trip, most of the travel time is spent on the highway between two cities. Passengers are not sensitive to small changes in intracity travel time. Therefore, this feature does not allow the platform to work in real time. Unlike intracity online car-hailing platforms that optimize driver and passenger matching and pricing, the platform mainly optimizes vehicle routes in daily operations. In the real world, passengers need to provide travel information to the platform several hours in advance.

Therefore, since there is no model in the current research that can fully represent the multi-objective vehicle routing problem for intercity travel, and given that the vehicle routing problem for intercity travel is essentially a multi-objective optimization problem, and the multi-objective optimization problem is one of the core problems in optimization problems, many scholars have studied it and proposed a variety of meta-heuristic method variants to solve multi-objective optimization problems in different situations. For most existing methods, effectively solving the optimization problem of multiple conflicting objectives is still a huge challenge. At the same time, in this problem, different objectives have different characteristics in physical meaning, scale and optimization difficulty. Therefore, for some objectives that are difficult to optimize using conventional neighborhood search operations, it is necessary to design neighborhood search operations for the objectives. Therefore, how to design an efficient algorithm framework for the intercity travel vehicle routing problem has high theoretical significance and application value.

Summary of the invention

The purpose of the present invention is to provide a method, system, electronic device and medium for determining a vehicle path for inter-city travel, which can provide a path planning solution that meets multiple needs for inter-city online car-hailing travel.

To achieve the above object, the present invention provides the following solutions:

A method for determining a path for an inter-city travel vehicle, the method comprising:

Taking maximizing the average number of passengers per trip, minimizing the number of vehicles, minimizing the total distance traveled by vehicles and minimizing the total waiting time of passengers as the objective function, and taking vehicle capacity, service quality, time constraints and safety constraints as constraints, an inter-city travel vehicle path model is constructed.

Obtaining intercity travel orders to be traveled; the intercity travel orders to be traveled include multiple travel orders; each of the travel orders includes the number of passengers, departure time, departure location and destination point;

According to the inter-city travel vehicle path model, the travel vehicles corresponding to each travel order are determined; wherein, one travel vehicle and multiple travel orders completed by the travel vehicle constitute a travel solution; multiple travel solutions constitute a travel external archive; and the travel external archive is used as the path planning solution for the inter-city order to be traveled.

Optionally, the objective function is:

f ₂ = |M _k |

Among them, the goal _f1 represents maximizing the average number of passengers per trip, _Mt and _Mk represent the number of trips t and vehicles k respectively, _Qt represents the occupancy rate of trip t, the goal _f2 represents minimizing the number of vehicles, the goal _f3 represents minimizing the total driving distance of vehicles, _Mt represents the number of trips t, _lt represents the total driving distance of trip t, It is used to determine whether trip t is arranged to vehicle k. Objective f ₄ represents minimizing the total waiting time of passengers.

Optionally, determining the travel vehicles corresponding to each of the travel orders according to the inter-city travel vehicle path model specifically includes:

According to the constraint conditions and the objective function, a plurality of itineraries to be traveled corresponding to each of the travel orders are determined; wherein each of the itineraries to be traveled includes at least one of the travel orders and each of the itineraries to be traveled satisfies the constraint conditions and the objective function;

According to the constraint conditions and the objective function, determine the vehicle corresponding to each of the to-be-traveled trips; wherein one of the vehicles and a plurality of the to-be-traveled trips completed by the vehicle constitute a solution; and a plurality of the solutions constitute an external archive;

Applying a neighborhood operation operator to each of the solutions to obtain search results corresponding to each of the solutions;

The ε-dominant archive update strategy is applied to each of the solutions and the search results corresponding to each of the solutions to obtain a travel external archive.

Optionally, determining a plurality of to-be-traveled trips corresponding to each of the travel orders according to the constraint conditions and the objective function specifically includes:

The travel order with the earliest departure time in the pre-processed order set is used as the benchmark order for the initial trip; the initial trip includes at least one travel order; the pre-processed order set includes multiple travel orders with the same departure location;

A preset pre-processed order is selected from the pending order set and added to the initial itinerary to obtain an updated initial itinerary and an order queue; the pending order set is the remaining orders after the pre-processed order set is removed from the benchmark order; the order queue is the remaining orders after one of the preset pre-processed orders is removed from the pending order set;

Determining whether the updated initial itinerary satisfies the constraint condition;

When the updated initial itinerary does not satisfy the constraint condition, the preset pre-processed order is deleted from the updated initial itinerary, and the process returns to the step of "selecting a preset pre-processed order from the pending order set and adding it to the initial itinerary to obtain an updated initial itinerary and order queue" for further execution;

When the updated initial trip satisfies the constraint condition, determining whether the number of passengers in the updated initial trip reaches the vehicle passenger capacity;

When the number of passengers in the updated initial trip reaches the passenger capacity of the vehicle, the updated initial trip is used as the final initial trip, and the travel orders in the final initial trip are deleted from the pre-processed order set to obtain an updated pre-processed order set;

When the number of passengers in the updated initial trip does not reach the passenger capacity of the vehicle, determining whether the number of travel orders in the order queue is 0;

When the number of travel orders in the order queue is not 0, the order queue is used as a pending order set, and the process returns to the step of "selecting a preset pre-processed order from the pending order set and adding it to the initial trip to obtain an updated initial trip and order queue";

When the number of travel orders in the order queue is 0, return to the step of "taking the updated initial itinerary as the final initial itinerary, and deleting the travel orders in the final initial itinerary from the pre-processed order set, to obtain an updated pre-processed order set";

When the number of travel orders in the updated pre-processed order set is not 0, the updated pre-processed order set is used as the pre-processed order set, and the process returns to the step of "using the travel order with the earliest departure time in the pre-processed order set as the benchmark order for the initial trip" to continue execution;

When the number of travel orders in the updated pre-processed order set is 0, the final initial itinerary is determined to be a plurality of to-be-traveled itineraries corresponding to each of the travel orders.

Optionally, determining the vehicle corresponding to each of the to-be-traveled trips according to the constraint condition and the objective function specifically includes:

The trip to be traveled with the earliest departure time in the pre-processed trip set is used as the reference trip of the vehicle; the vehicle includes at least one trip to be traveled; the pre-processed trip set includes multiple trips to be traveled with the same departure point;

A preset pre-processed trip is selected from the to-be-processed trip set and added to the initial trip to obtain an updated vehicle and trip queue; the to-be-processed trip set is the remaining trip after the pre-processed trip set is removed from the reference trip; the trip queue is the remaining trip after one of the preset pre-processed trips is removed from the to-be-processed trip set;

Determining whether the updated vehicle satisfies the constraint condition;

When the updated vehicle does not satisfy the constraint condition, the preset pre-processed trip is deleted from the updated vehicle, and the process returns to the step of "selecting a preset pre-processed trip from the set of trips to be processed and adding it to the vehicle to obtain an updated vehicle and trip queue" to continue the execution;

When the updated vehicle satisfies the constraint condition, the updated vehicle is used as the final vehicle, and the to-be-traveled trips in the final vehicle are deleted from the pre-processed trip set to obtain an updated pre-processed trip set;

Determine whether the number of pending trips in the trip queue is 0;

When the number of pending trips in the trip queue is not 0, the trip queue is used as a pending trip set, and the process returns to the step of "selecting a preset pre-processed trip from the pending trip set and adding it to the vehicle to obtain an updated vehicle and trip queue";

When the number of pending trips in the trip queue is 0, return to the step of "selecting a preset pre-processed trip from the pending trip set to add to the initial trip to obtain an updated vehicle and trip queue";

Determine whether the number of pending trips in the updated pre-processed trip set is 0;

When the number of to-be-traveled trips in the updated pre-processed trip set is not 0, the updated pre-processed trip set is used as the pre-processed trip set, and the process returns to the step of "using the to-be-traveled trip with the earliest departure time in the pre-processed trip set as the reference trip of the vehicle" to continue the execution;

When the number of the to-be-traveled trips in the updated pre-processed trip set is 0, the final vehicle is determined to be a plurality of to-be-traveled trips corresponding to the to-be-traveled trips.

Optionally, applying a neighborhood operation operator to each of the solutions to obtain search results corresponding to each of the solutions specifically includes:

Applying a plurality of neighborhood operation operators to search for each of the solutions to obtain a plurality of initial search results corresponding to each of the solutions;

Calculating the lift corresponding to each of the solutions according to the plurality of initial search results;

When the number of searches is less than the preset number, returning to the step of "applying a neighborhood operation operator to the preset solution in the solution to obtain an initial search result" to continue execution;

When the number of searches is greater than or equal to a preset number of times, calculating an improved crowding distance of each solution according to each solution and the initial search result corresponding to each solution;

Normalizing the improved crowding distance of each solution to obtain the solution selection probability of each solution;

Determining the operation selection probability of each neighborhood operation operator according to the lifting degree corresponding to each of the solutions;

Selecting a solution to be processed from a plurality of solutions according to a solution selection probability;

Determining a target neighborhood operation from a plurality of neighborhood operation operators according to the operation selection probability;

Applying the target neighborhood operation to perform a local search on the solution to be processed, and obtaining a final search result corresponding to the solution to be processed;

The initial search results are updated according to the final search results to obtain search results corresponding to each of the solutions.

A system for determining a path for an inter-city travel vehicle, applying the above-mentioned method for determining a path for an inter-city travel vehicle, the determination system comprising:

A construction module is used to construct an inter-city travel vehicle path model with the objective function of maximizing the average number of passengers per trip, minimizing the number of vehicles, minimizing the total vehicle travel distance and minimizing the total passenger waiting time, and with the vehicle passenger capacity, service quality, time constraint and safety constraint as constraints;

An acquisition module is used to acquire inter-city travel orders to be traveled; the inter-city travel orders to be traveled include multiple travel orders; each of the travel orders includes the number of passengers, departure time, departure location and destination point;

A solution determination module is used to determine the travel vehicles corresponding to each travel order according to the inter-city travel vehicle path model; wherein, one travel vehicle and multiple travel orders completed by the travel vehicle constitute a travel solution; multiple travel solutions constitute a travel external archive; and the travel external archive is used as the path planning solution for the inter-city order to be traveled.

An electronic device includes a memory and a processor, wherein the memory is used to store a computer program, and the processor runs the computer program to enable the electronic device to execute the above-mentioned method for determining a vehicle path for inter-city travel.

A computer-readable storage medium stores a computer program, which, when executed by a processor, implements the above-mentioned method for determining a vehicle path for inter-city travel.

According to the specific embodiments provided by the present invention, the present invention discloses the following technical effects:

The present invention defines the inter-city online car-hailing route optimization problem as a multi-objective problem with four objectives, with maximizing the average number of passengers per trip, minimizing the number of vehicles, minimizing the total vehicle driving distance and minimizing the total waiting time of passengers as the objective function, and with vehicle passenger capacity, service quality, time constraints and safety constraints as constraints, to construct an inter-city travel vehicle route model; and solve the inter-city travel vehicle route model based on the inter-city orders to be traveled, and determine the travel vehicles corresponding to each travel order; the present invention can more comprehensively and truly reflect the essence of the inter-city travel problem, and provide a route planning solution that meets multiple needs for inter-city online car-hailing travel.

BRIEF DESCRIPTION OF THE DRAWINGS

In order to more clearly illustrate the embodiments of the present invention or the technical solutions in the prior art, the drawings required for use in the embodiments will be briefly introduced below. Obviously, the drawings described below are only some embodiments of the present invention. For ordinary technicians in this field, other drawings can be obtained based on these drawings without paying creative labor.

FIG1 is a flow chart of a method for determining a vehicle path for inter-city travel according to the present invention;

FIG2 is a flow chart of an adaptive local search method for solving a multi-objective intercity travel vehicle routing problem according to the present invention.

FIG3 is a flow chart of the initialization construction method based on time series of the present invention.

DETAILED DESCRIPTION

The following will be combined with the drawings in the embodiments of the present invention to clearly and completely describe the technical solutions in the embodiments of the present invention. Obviously, the described embodiments are only part of the embodiments of the present invention, not all of the embodiments. Based on the embodiments of the present invention, all other embodiments obtained by ordinary technicians in this field without creative work are within the scope of protection of the present invention.

The purpose of the present invention is to provide a method, system, electronic device and medium for determining a vehicle path for inter-city travel, which can provide a path planning solution that meets multiple needs for inter-city online car-hailing travel.

The present invention has particularities in terms of selecting optimization objectives, driving safety, and fatigue driving restrictions. Therefore, it is intended to analyze the various constraints of intercity travel in practical applications, and to build a path optimization model with certain universality in combination with the characteristics of intercity travel. It is committed to establishing a comprehensive and practical universal multi-objective path optimization model for the multi-objective characteristics and practical applications of intercity travel vehicle path problems, and to construct a test case for intercity travel cases based on real-world data. And design neighborhood search operations for each goal, and finally combine a learning-based adaptive selection framework to solve the intercity travel vehicle path problem, so as to ultimately plan the travel path of intercity online car-hailing efficiently and intelligently, bringing a comfortable travel experience to travelers, saving transportation costs, and bringing more benefits to companies and drivers. In the intercity online car-hailing industry, the planning of travel path plans is one of the key issues in online car-hailing services.

In the present invention, it is intended to complete the two-stage allocation of allocating orders to trips and allocating trips to vehicles (travel tasks). By optimizing the vehicle route, the total vehicle driving distance, the total passenger waiting time, the maximum travel occupancy rate and the number of vehicles are minimized. Therefore, an initialization construction method based on time series is proposed to generate an initialization planning scheme. In this method, based on the random selection of time sequence, it is possible to ensure that the planning scheme is obtained without allowing the planning scheme to converge prematurely, and it has diversity while achieving relatively good solution quality. At the same time, it should be noted that since the research model of the present invention is an inter-city travel scenario, there are two types of order sets (i.e., the order set Ord ₁ from city a to city b and the order set Ord ₂ from city b to city a, and the trip set Trips ₁ /Trips ₂ and vehicle set Car ₁ /Car ₂ obtained on this basis are also two types).

In order to make the above-mentioned objects, features and advantages of the present invention more obvious and easy to understand, the present invention is further described in detail below with reference to the accompanying drawings and specific embodiments.

Embodiment 1

As shown in FIG1 , the present invention provides a method for determining a path of an inter-city travel vehicle, the method comprising:

Step S1: Taking maximizing the average number of passengers per trip, minimizing the number of vehicles, minimizing the total vehicle travel distance and minimizing the total passenger waiting time as the objective function, and taking vehicle passenger capacity, service quality, time constraints and safety constraints as constraints, an inter-city travel vehicle path model is constructed.

Specifically, the objective function is:

Among them, the goal _f1 represents maximizing the average number of passengers per trip, _Mt and _Mk represent the number of trips t and vehicles k respectively, _Qt represents the occupancy rate of trip t, the goal _f2 represents minimizing the number of vehicles, the goal _f3 represents minimizing the total driving distance of vehicles, _Mt represents the number of trips t, _lt represents the total driving distance of trip t, It is used to determine whether trip t is arranged to vehicle k. Objective f ₄ represents minimizing the total waiting time of passengers.

The path planning problem of intercity online ride-hailing can be defined as a private company has developed a platform to provide intercity ride-sharing (IRS) services for passengers between two cities. Passengers between the two cities need to provide their travel information to the platform a few hours in advance. The specific description is: a group of orders (denoted as C = {1, 2, ..., n}) are served by companies with the same seat size of online ride-hailing vehicles. Each order has a number of passengers, i.e., demand q _i and a departure time window [b _i , e _i ], and can only be served by one vehicle, and each vehicle belongs to the city where the vehicle's starting point and destination are located. The vehicle plans the pick-up route according to the boarding and alighting points of each order, and sends the passengers of each order to the corresponding boarding and alighting points in turn. And it is required that any vehicle k∈K needs to let all passengers of each trip get off before picking up the next new passenger. Considering the characteristics of intercity travel, the time information of the passenger order of the present invention is a soft time window, that is, the difference later than the latest departure time is defined as the waiting time of the passenger. At the same time, in order to ensure driving safety, each driver must take a minimum of 20 minutes of rest within the 4 hours of continuous driving time stipulated by the state. At the same time, the number of passengers for each order cannot exceed the maximum passenger capacity of the vehicle, and the total number of passengers for all orders assigned to the same trip cannot exceed the maximum passenger capacity of the vehicle.

The model of the inter-city online car-hailing route planning problem contains multiple constraints, which are defined as follows:

1) Capacity constraint: The number of passengers served by all vehicles does not exceed the maximum passenger capacity, that is, the number of passengers in each order cannot exceed the maximum passenger capacity of the vehicle and the total number of passengers in all orders assigned to the same trip cannot exceed the maximum passenger capacity of the vehicle. That is, it satisfies:

in, represents the number of passengers in the pth order of trip t, and M _t represents the number of trips t of the vehicle.

2) Service Constraint 1: In order to ensure the service quality of online ride-hailing, any vehicle k∈K needs to get off all passengers on this route before picking up the next batch of new passengers. That is, it satisfies:

in, represents the current number of passengers after vehicle k has completed its service to pick up j, is a 0-1 variable used to determine whether the pick-up point i is assigned to vehicle k. is a 0-1 variable used to determine whether trip t is scheduled to vehicle k. is a 0-1 variable that determines whether the starting point i is the last pick-up point of trip t. It can be seen that this formula is valid if and only if That is, the pick-up point j served by vehicle k is the last pick-up point of the trip, so at this time It means that the number of passengers after vehicle k serves the last pick-up point j is 0.

3) Service constraint 2: Each order is served by one vehicle.

in, is a 0-1 variable used to determine whether order p is assigned to vehicle k.

4) Service Constraint Three: In inter-city travel, the pick-up and drop-off points of any order will only appear on one and the same route, and the pick-up point of an order in the departure city must appear before the drop-off point of the order in the destination city.

in, It is a 0-1 variable used to determine whether the pick-up point i, j is assigned to order p. is a 0-1 variable used to determine whether order p is assigned to vehicle k. represents the time when vehicle k arrives at pick-up point i.

5) Service constraint 4: All vehicles shall serve a location no more than once in one trip.

in, is a 0-1 variable used to determine whether pick-up point i is scheduled for trip t.

6) Service constraint five: means that all vehicles that serve the passenger’s departure point must also serve the passenger’s destination.

in, It is a 0-1 variable used to determine whether the pick-up point i, j is assigned to order p. is a 0-1 variable used to determine whether order p is assigned to vehicle k. It is a 0-1 variable used to determine whether the pick-up point i is assigned to vehicle k.

7) Time constraints: In order to ensure the service quality of inter-city online ride-hailing services, the start time of service must meet the service time window. That is, it must meet:

in, is a 0-1 variable used to determine whether order p is assigned to vehicle k. e _P represents the latest service start time of order p. represents the time when vehicle k arrives at pick-up point i. _{b P} represents the earliest service start time of order p.

8) Safety constraints: Considering that the driving time of an inter-city trip is longer than that of an intra-city trip, in order to ensure the safety of passengers and drivers during inter-city online car-hailing trips and to ensure the travel efficiency of drivers, all vehicles are required to take the minimum rest time prescribed by the state after reaching the maximum continuous driving time prescribed by the state. That is, it meets:

in, represents the time when vehicle k arrives at pick-up point i, ti _,j represents the driving time of the vehicle from pick-up point i to pick-up point j, _gi represents the service time, and _TR represents the minimum rest time required by the state for continuous driving time. is a 0-1 decision variable used to determine whether the continuous driving time of vehicle k when it arrives at pick-up point i exceeds the prescribed maximum continuous driving time. In China, the prescribed maximum continuous driving time is 4 hours.

Step S2: Obtain intercity travel orders to be traveled; the intercity travel orders to be traveled include multiple travel orders; each of the travel orders includes the number of passengers, departure time, departure location and destination point.

Step S3: Determine the travel vehicles corresponding to each travel order according to the inter-city travel vehicle path model; wherein, one travel vehicle and multiple travel orders completed by the travel vehicle constitute a travel solution; multiple travel solutions constitute a travel external archive; and use the travel external archive as the path planning solution for the inter-city order to be traveled.

S3 specifically includes:

Step S31: determining a plurality of itineraries to be traveled corresponding to each of the travel orders according to the constraints and the objective function; wherein each of the itineraries to be traveled includes at least one of the travel orders and each of the itineraries to be traveled satisfies the constraints and the objective function.

S31 specifically includes:

Step S3100: taking the travel order with the earliest departure time in the pre-processed order set as the benchmark order for the initial trip; the initial trip includes at least one travel order; the pre-processed order set includes multiple travel orders with the same departure point.

Step S3101: Select a preset preprocessed order from the pending order set and add it to the initial itinerary to obtain an updated initial itinerary and order queue; the pending order set is the remaining orders after removing the benchmark order from the preprocessed order set; the order queue is the remaining orders after removing one of the preset preprocessed orders from the pending order set.

Step S3102: Determine whether the updated initial itinerary satisfies the constraint condition.

Step S3103: When the updated initial itinerary does not satisfy the constraint condition, the preset pre-processed order is deleted from the updated initial itinerary, and the process returns to the step of "selecting a preset pre-processed order from the set of pending orders and adding it to the initial itinerary to obtain an updated initial itinerary and order queue" to continue execution.

Step S3104: When the updated initial trip satisfies the constraint condition, it is determined whether the number of passengers in the updated initial trip reaches the vehicle passenger capacity.

Step S3105: When the number of passengers in the updated initial trip reaches the passenger capacity of the vehicle, the updated initial trip is used as the final initial trip, and the travel orders in the final initial trip are deleted from the pre-processed order set to obtain an updated pre-processed order set.

Step S3106: When the number of passengers in the updated initial trip does not reach the passenger capacity of the vehicle, determine whether the number of travel orders in the order queue is 0.

Step S3107: When the number of travel orders in the order queue is not 0, the order queue is used as a pending order set, and the process returns to the step of "selecting a preset pre-processed order from the pending order set and adding it to the initial trip to obtain an updated initial trip and order queue".

Step S3108: When the number of travel orders in the order queue is 0, return to the step of "taking the updated initial itinerary as the final initial itinerary, and deleting the travel orders in the final initial itinerary from the pre-processed order set to obtain an updated pre-processed order set".

Step S3109: When the number of travel orders in the updated pre-processed order set is not 0, the updated pre-processed order set is used as the pre-processed order set, and the process returns to the step of "using the travel order with the earliest departure time in the pre-processed order set as the benchmark order for the initial trip" to continue execution.

Step S3110: When the number of travel orders in the updated pre-processed order set is 0, determining that the final initial itinerary is a plurality of to-be-traveled itineraries corresponding to each of the travel orders.

In practical applications, as shown in FIG3 , determining a plurality of to-be-traveled trips corresponding to each of the travel orders is based on an initialization construction method of a time series, and includes the following seven steps:

Step 1: Sort the two order sets Ord ₁ /Ord ₂ in ascending order according to the earliest departure time of the order, and select the first order o ₁ in the pending order set Ord ₁ /Ord ₂ as the benchmark to generate a trip node vector t. Remove order o ₁ from the pending order set Ord ₁ /Ord _2. Add the orders in the pending order set Ord ₁ /Ord ₂ to the order queue S, and set the status of all orders to "unprocessed".

In practical applications, a path planning scheme X is represented by a set of k routes O = {o1,..oi...,ok}, where is a path consisting of a visit sequence containing Ni orders and 2Ni pick-up and drop-off points. represents the jth customer point of the i-th path. Since each order contains the customer's pick-up point in the departure city and the drop-off point in the target city, each order is represented as two pick-up points in each path, namely the pick-up point in the departure city and the drop-off point in the target city. In a path planning scheme, the two pick-up points of any order will only appear in one and the same path.

Step 2: Randomly select order o from the current pending order set Ord ₁ /Ord ₂ and add it to t, and set the status of order o to "processed". At the same time, check whether the trip t after order o is added meets the model constraints. If so, proceed to step 3. If not, remove order o from trip t and return to step 2.

Step 3: Check whether the sum of the number of passengers currently added to the trip t reaches the vehicle capacity. If so, proceed to step 4; if not, proceed to step 6.

Step 4: Add t to the itinerary set Trips ₁ /Trips ₂ , remove the order of itinerary t from the pending order set Ord ₁ /Ord ₂ , and clear t at the same time.

Step 5: Determine whether the pending order set Ord ₁ /Ord ₂ is empty. If so, proceed to step 7. If not, return to step 1.

Step 6, determine whether there is an order in the order queue S with an order status of "unprocessed". If so, return to step 2; if not, return to step 4.

Step 7: Initialize the trip set Trips ₁ /Trips ₂ successfully.

Step S32: Determine the vehicle corresponding to each of the to-be-traveled trips according to the constraint conditions and the objective function; wherein one of the vehicles and a plurality of the to-be-traveled trips completed by the vehicle constitute a solution; and a plurality of the solutions constitute an external archive.

S32 specifically includes:

Step S3201: taking the trip to be traveled with the earliest departure time in the pre-processed trip set as the reference trip of the vehicle; the vehicle includes at least one trip to be traveled; the pre-processed trip set includes multiple trips to be traveled with the same departure point.

Step S3202: Select a preset pre-processed trip from the set of trips to be processed and add it to the initial trip to obtain an updated vehicle and trip queue; the set of trips to be processed is the remaining trips after removing the reference trip from the pre-processed trip set; the trip queue is the remaining trips after removing one of the preset pre-processed trips from the set of trips to be processed.

Step S3203: Determine whether the updated vehicle satisfies the constraint condition.

Step S3204: When the updated vehicle does not satisfy the constraint condition, the preset pre-processed trip is deleted from the updated vehicle, and the process returns to the step of "selecting a preset pre-processed trip from the set of trips to be processed and adding it to the vehicle to obtain an updated vehicle and trip queue" to continue execution.

Step S3205: When the updated vehicle satisfies the constraint condition, the updated vehicle is used as the final vehicle, and the to-be-traveled trips in the final vehicle are deleted from the pre-processed trip set to obtain an updated pre-processed trip set.

Step S3206: Determine whether the number of pending trips in the trip queue is 0.

Step S3207: When the number of pending trips in the trip queue is not 0, the trip queue is used as a pending trip set, and the process returns to the step of "selecting a preset pre-processed trip from the pending trip set and adding it to the vehicle to obtain an updated vehicle and trip queue".

Step S3208: When the number of pending trips in the trip queue is 0, return to the step of "selecting a preset pre-processed trip from the pending trip set and adding it to the initial trip to obtain an updated vehicle and trip queue".

Step S3209: Determine whether the number of pending trips in the updated pre-processed trip set is 0.

Step S3210: When the number of to-be-traveled trips in the updated pre-processed trip set is not 0, the updated pre-processed trip set is used as the pre-processed trip set, and the process returns to the step of "using the to-be-traveled trip with the earliest departure time in the pre-processed trip set as the vehicle's reference trip" to continue execution.

Step S3211: when the number of the to-be-traveled trips in the updated pre-processed trip set is 0, determining that the final vehicle is a plurality of to-be-traveled trips corresponding to each of the to-be-traveled trips.

In practical applications, as shown in FIG3 , the process of determining the vehicle corresponding to each of the to-be-traveled trips specifically includes:

Step 1: Sort the two trip sets Trips ₁ /Trips ₂ in ascending order according to the earliest start time of the trip.

Step 2: Select the first trip t ₁ of the pending trip set Trips ₁ /Trips ₂ as a reference to generate a vehicle node vector c. Remove trip t ₁ from the pending trip set Trips ₁ /Trips _2. Add the trips in the pending trip set Trips ₁ /Trips ₂ to the trip queue T, and set the status of all trips to "unprocessed".

Step 3: Randomly select trip t from the current set of pending trips Trips ₁ /Trips ₂ and add it to c, set the status of trip t to "processed", and check whether the vehicle c after adding trip t meets the model constraints. If yes, go to step 4; if not, remove trip t from vehicle c and return to step 3.

Step 4: Determine whether there is a trip in the trip queue T with a status of "unprocessed". If so, return to step 3; if not, proceed to step 5.

Step 5: add c to the vehicle set Car ₁ /Car ₂ , remove the trip of vehicle c from the pending trip set Trips ₁ /Trips ₂ , and clear c. Determine whether the pending trip set Trips ₁ /Trips ₂ is empty. If so, proceed to step 6. If not, return to step 2.

Step 6: Initialize the vehicle set Car ₁ /Car ₂ successfully (all vehicles in the two vehicle sets constitute a solution).

Step S33: applying a neighborhood operation operator to each of the solutions to obtain search results corresponding to each of the solutions.

Specifically, the neighborhood operation operators provided by the present invention are eight neighborhood operation operators, which are:

Neighborhood operation 1: delete and then insert operation for a single customer point. Neighborhood operation 2: exchange operation for a single customer point. Neighborhood operation 3: delete and then insert operation for multiple customer points. Neighborhood operation 4: delete and then insert operation for multiple exchanges. Neighborhood operation 5: delete and then insert operation for a single trip. Neighborhood operation 6: exchange operation for a single trip. Neighborhood operation 7: delete and then insert operation for multiple trips. Neighborhood operation 8: exchange operation for multiple trips.

Furthermore, the present invention designs eight neighborhood operation operators targeting the characteristics of intercity travel problems to perform local search optimization for solutions. Given that the vehicle routing problem for intercity travel is essentially a multi-objective optimization problem, and the multi-objective optimization problem is one of the core problems in optimization problems, in which different objectives have different characteristics in terms of physical meaning, scale, and optimization difficulty. Therefore, for some objectives that are difficult to optimize using conventional neighborhood search operations, it is necessary to design neighborhood search operations targeting the characteristics of intercity travel. The specific definitions are as follows:

Neighborhood operation 1: Delete a customer point and reinsert it to the optimal position. Randomly select a customer point on a path to delete it and reinsert it to the optimal position. The order of the drop-off points on the path is determined by the polar angle sorting method. Specifically, the order of the drop-off points is rearranged after calculating the polar angles of the drop-off points and sorting them (the following neighborhood operations will readjust the drop-off routes of the customer points, and the methods used are the same).

Neighborhood operation 2: Exchange a single customer point. First, randomly select a customer point on a path to exchange. Second, try to exchange this customer point with customer points on other paths in turn. Record the delta value, which is the value of the target after optimization. Third, compare and get the min_delta value, and exchange this customer point with the customer point that gets the minimum value of the target at this time.

Neighborhood operation three: Delete multiple customer points and reinsert them into the optimal position. Randomly select multiple customer points on a path to delete and reinsert them into the optimal position.

Neighborhood operation 4: Exchange multiple customer points (two-opt operation). First, randomly select a customer point on a path as the starting point for exchange. Second, select a customer point on another path as the starting point for the second exchange in turn, and try to exchange the path starting from the customer point on the exchange path with the path starting from the customer point on the exchange path. Record the delta value, which is the value of the target after optimization. Third, compare and get the min_delta value, and exchange the path starting from the customer point with the customer point that gets the minimum value of the target at this time.

Neighborhood operation 5: Delete a path and insert the customer points on the path into other paths (delete and then insert for a single trip). The first step is to randomly select a path (assuming it is the path trip_ind). The second step is to try to insert each customer point on the path into other paths. 1: If all customer points on the path cannot be deleted and inserted successfully, the restore path returns false. 2: If all customer points on the path are deleted and inserted successfully, the path trip_ind is now an empty path. There are two cases to consider:

2-1: If the path trip_ind is the last path of the vehicle, then the path trip_ind can be deleted directly. Return true.

2-2: If the path trip_ind is not the last path of the vehicle, it is necessary to check whether the path trip_next after the path trip_ind can also be turned into an empty path in the same way, that is, try to insert each customer point on the path trip_next into other paths. If the customer points on the path trip_next cannot be deleted and inserted successfully, restore the paths trip_ind and trip_next and return false. If the customer points on the path trip_next are all deleted and inserted successfully, the path trip_next is now an empty path. Then the paths trip_ind and trip_next can be deleted and true is returned.

Neighborhood operation six: swapping a single trip. First, randomly select two different paths on two vehicles to swap. Second, swap the two paths. Record the delta value, which is the value of the target after optimization. Third, if the delta value is smaller than the original target value, swap the two paths.

Neighborhood operation seven: Delete a vehicle and insert its return trip into other vehicles (delete and then insert for multiple trips). The first step is to select a vehicle car_ind with the least number of current paths. The second step is to try to traverse and insert other vehicles into the paths on the vehicle in units of return trips or special single trips (this trip has no next trip). (1) If the paths on the vehicle cannot be deleted and inserted successfully, the restoration vehicle returns false. (2) If the paths on the vehicle are deleted and inserted successfully, the vehicle car_ind is an empty path. Then the vehicle car_ind can be deleted and true is returned.

Neighborhood operation eight: exchange a single return trip (exchange multiple trips). First, randomly select two different return trips on two vehicles to exchange. Second, exchange the two return trips. Record the delta value, which is the value of the target after optimization. Third, if the delta value is smaller than the original target value, exchange the two return trips.

In the present invention, regarding the application of local search, the following strategies are adopted: probability + probability strategy: each time according to the potential values of different solutions, a solution is selected from the external archive solution set EP with probability, and according to the contribution of each neighborhood operation, a neighborhood operation mode is selected with probability to perform a deep local search. Among them, regarding the contribution of the neighborhood operation, it should be more related to its contribution to convergence, that is, the improvement of each target value. Therefore, the selection probability of each neighborhood operation can be defined as the contribution to the convergence of the external archive within the L window (nearly L searches), where L is defined as the number of selected rounds of each neighborhood operation, and a matrix is set to maintain the probability list. Regarding the potential value of the external archive solution, since the solution set is a non-dominant set, its potential value reflects the potential for diversity, so the selection probability of each solution can be defined as the crowding distance. That is, the present invention adopts an adaptive local search strategy to generate a new path planning scheme. The specific definitions are as follows:

1. Definition of the potential value of the solution: Regarding the potential value of the external archived solution, since the solution set is a non-dominant set, its potential value reflects the potential for diversity, so the potential value of each solution can be defined as the crowding distance. Because the calculation method most commonly used today is the crowding distance calculation method in NSGA-II, it is simple and fast, but because the crowding distance is calculated by sorting according to an objective function, the final retained solution set is only uniformly distributed on the objective function, and there is an uneven situation on other functions. Therefore, on this basis, the improved crowding distance calculation method is selected, and its calculation formula is as follows:

in: It represents the m-th dimension objective function value of the next particle of the ith example after sorting the m-th dimension objective function values from small to large; It represents the m-th dimension objective function value of the particle before the i-th particle after the m-th dimension objective function value is sorted from small to large. The improved crowding distance calculation method not only still only considers the two particles before and after, but also comprehensively considers each dimension of objective function, which is more reasonable. In addition, it should be noted that when i＝1 or i＝N, dis _i ＝inf. If these two extreme value solutions are considered, the probability of solution selection in the subsequent calculation formula can be regarded as 100% (mandatory), and because these two extreme value solutions can be regarded as elite solutions in practical significance, these two extreme value solutions are directly saved in the external archive and do not participate in the subsequent solution selection.

Thus, based on dis _i, we can get PV _i (the probability of selecting the i-th solution in EP):

Where n is the number of solutions in the current EP, and ε is the minimum probability of being selected, ensuring that each solution has a chance to be used during the entire local search process.

2. Definition of the contribution of neighborhood operations: Regarding the contribution of neighborhood operation search, it should be more about its contribution to convergence. Therefore, the selection probability of the kth neighborhood operation can be defined as the contribution to the convergence of the external archive within the L window, that is, the improvement of each target value DOI _k (Degree of improvement):

Among them, _Obj'i represents the i-th target value of the solution after the neighborhood operation after normalization, and Obj _i represents the i-th target value of the solution before the neighborhood operation after normalization. Num represents the number of targets in the model, which should be 4 here. At the same time, it should be noted that this calculation formula is used only when the solution after the neighborhood operation optimization enters the external archive solution set EP update, and DOI _k is 0 in other cases. The normalization of the target value adopts the deviation standardization formula, which is a linear transformation of the original data so that the result falls into the [0,1] interval. The conversion function is as follows:

Among them, _fi represents the i-th objective value of the solution before the neighborhood operation, max _i and min _i represent the maximum value of the i-th objective among all solutions in EP and the minimum value of the i-th objective among all solutions in EP, respectively.

Thus, based on DOI _k, we get LS _k (the probability of selection of the kth neighborhood operation):

Among them, gen represents the number of times the neighborhood operation is currently selected, and ε is the set minimum selection probability. It ensures that each neighborhood operation operator has the opportunity to be used during the entire local search process.

S33 specifically includes:

Step S3301: Apply multiple neighborhood operation operators to search for each of the solutions to obtain multiple initial search results corresponding to each of the solutions.

Step S3302: Calculate the lift corresponding to each of the solutions based on the multiple initial search results.

Step S3303: When the number of searches is less than the preset number, return to the step of "applying a neighborhood operation operator to the preset solution in the solution to obtain an initial search result" to continue execution.

Step S3304: when the number of searches is greater than or equal to a preset number of searches, the improved crowding distance of each solution is calculated according to each solution and the initial search result corresponding to each solution.

Step S3305: normalize the improved crowding distance of each solution to obtain the solution selection probability of each solution.

Step S3306: Determine the operation selection probability of each neighborhood operation operator according to the lifting degree corresponding to each solution.

Step S3307: Select a solution to be processed from the multiple solutions according to the solution selection probability.

Step S3308: Determine a target neighborhood operation from the plurality of neighborhood operation operators according to the operation selection probability.

Step S3309: Apply the target neighborhood operation to perform a local search on the solution to be processed to obtain a final search result corresponding to the solution to be processed.

Step S3310: updating the initial search results according to the final search results to obtain search results corresponding to each of the solutions.

In practical applications, as shown in FIG2 , the specific process of obtaining the search results corresponding to each solution is as follows:

Step 1: randomly select a solution in the external archive EP, randomly select a neighborhood operator _LSn (n=1...8) with an average probability of (1/8) to perform local search, and simultaneously update the external archive solution set EP using ε dominance.

Step 2: The number of searches _mn of the neighborhood operation _LSn is increased by one, and the improvement of the neighborhood operation is calculated and the result is saved in the learning matrix.

Step 3: determine whether the number of searches for the neighborhood operation m _n is less than m times. If so, return to step 1; if not, proceed to step 4. In practical applications, m is a preset value; optionally, the value of m can be determined based on experience or preliminary experiments.

Step 4: Perform improved crowding distance calculation on each solution in the external archive solution set EP, and normalize it to obtain the selection probability of each solution. At the same time, the selection probability of each neighborhood operation is obtained based on the learning matrix according to the calculation formula of LS _k .

Step 5: For the external archive solution set EP, a solution is selected from it according to the solution selection probability, and then a neighborhood operation is selected according to the operation probability to perform a deep local search.

Step 6: Use ε-dominance to update the external archive solution set EP and update the learning matrix. Return to step 4.

Specifically, the deep local search operation process includes the following steps:

Step 1: Set the number of searches m=0, and the maximum search depth to D. Wherein D is a preset value; optionally, the value of D can be determined based on experience or preliminary experiments.

Step 2: Perform neighborhood operation on the selected solution to determine whether the solution after the neighborhood search operation can enter the external archive EP. If it is satisfied, return to step 1; if not, proceed to step 3.

Step 3, add 1 to the number of searches m to determine whether the number of searches m is equal to D. If so, end the process; if not, return to step 2.

Step S34: applying the ε-dominant archive update strategy to each of the solutions and the search results corresponding to each of the solutions to obtain a travel external archive.

In practical applications, the ε-dominant archive update strategy includes:

If Archive is empty, the generated path planning solution X _new is added to Archive. Archive is a term defined in the theory of multi-objective optimization algorithms, which means archiving, that is, it is used to store the excellent individuals generated in each generation during the algorithm optimization process, that is, non-dominated solutions.

If Archive is not empty, the generated path planning scheme X _new is compared with the existing path planning schemes for ε-dominance; if there is an existing scheme that is superior to X _new or is the same as X _new , X _new is discarded; if X _new is superior to the existing path planning schemes, all the superior schemes are deleted and X _new is added to Archive; if X _new is not superior to all the path planning schemes, X _new is added to Archive.

Specifically, each non-dominant solution in the archive is assigned an association vector B = {B ₁ ,B ₂ ,…,B ₄ }, where 4 represents the number of optimization objectives. The parameter variable ε is used to control the size of the archive.

Archive update strategy: In the multi-objective intercity online car-hailing route planning problem, the comparison between route planning schemes is carried out through the multi-objective dominance relationship. The definition of the dominance relationship involved in the present invention is as follows: For route planning schemes X and Y, if

1) For all target values, f _j (X) ≤ f _j (Y), j = 1, 2.

2) There exists at least one j such that f _j (X) < f _j (Y).

If the above two conditions are met at the same time, then X is said to dominate Y; otherwise, X and Y are said to be non-dominant solutions.

In addition, based on the multi-objective dominance relationship, an ε-dominance strategy is added to limit the size of the external archive during the search process. In the ε-dominant archive, each non-dominant solution in the archive corresponds to an association vector B = {B ₁ , B ₂ , B ₃ , B ₄ }, where _Bi = log( _fi +1)/log(1+ε), and each hypercube stores a non-dominant solution. Therefore, the archive based on ε-dominance not only makes the non-dominant solutions evenly distributed, but also limits the size of the external archive during the search process.

According to the definition of the above dominant relationship, the archive update strategy for the multi-objective intercity online car-hailing path planning problem solved by the present invention is as follows: if Archive is empty, the generated path planning solution X _new is added to Archive.

If Archive is not empty, the generated path planning scheme X _new is compared with the existing path planning schemes for ε-dominance; if there is an existing scheme that is superior to X _new or is the same as X _new , X _new is discarded; if X _new is superior to the existing path planning schemes, all the superior schemes are deleted and X _new is added to Archive; if X _new is not superior to all the path planning schemes, X _new is added to Archive.

When the present invention is actually applied, after obtaining the intercity travel order to be traveled, the following operations are performed:

(1) Sort the two order sets in ascending order according to the earliest departure time of the orders, generate a trip that satisfies the constraints according to the method, complete the initialization of the two trip sets and sort them in ascending order according to the earliest start time of the trip, generate vehicles (travel tasks, the same below) that meet the constraints according to the method, complete the allocation of the two vehicle sets, generate an initial feasible planning scheme, and update the scheme to the external archive solution set EP.

(2) Determine whether the initialization number n reaches the set maximum number of cycles n _max . If so, proceed to step (3); otherwise, return to step (1). The maximum number of cycles n _max is a preset value; optionally, the maximum number of cycles n _max can be determined based on experience or preliminary experiments.

(3) For the path planning solutions in the external archive solution set EP, eight neighborhood operation operators designed based on the characteristics of inter-city travel are used to perform an adaptive local search strategy to update EP.

(4) Determine whether the running time h reaches the set maximum running time h _max . If so, proceed to step (5); otherwise, return to step (3).

(5) According to the decision maker's needs (based on the actual needs of the four objectives), a path planning solution in the external archive solution set EP is selected, and each path sequence in the solution is assigned to the vehicle (driver) corresponding to the path sequence.

Because the currently widely used examples have two defects in the inter-city travel path optimization problem: first, the driving distance and driving time between customer points in the data set are too idealized. It relies on the Euclidean distance and assumes that the triangle inequality relationship is satisfied, but in the real world, it is often not in direct proportion and does not necessarily satisfy the triangle inequality. Second, in this example, there is a weak correlation between its objectives, so it cannot be applied in the study of multi-objective optimization. Due to the lack of test examples suitable for the vehicle path problem for inter-city travel in this study, and in order to further verify the effectiveness of the model and algorithm proposed in this study. Therefore, the present invention designs a test example for the vehicle path problem for inter-city travel suitable for this study: the test is based on the real order data of a certain inter-city online car-hailing platform. The test example is specifically defined as follows:

Based on the data of the actual scene of a certain online car-hailing platform in Xiamen, the actual order data between Xiamen and Zhangzhou was selected to design a test case. The coordinates of the customer point and the garage were generated based on the actual location. At the same time, the driving time and driving distance between any two points were calculated based on the actual road network. The actual road network can be Baidu Map, which can obtain data that is more in line with the actual travel rules. The distance is accurate to meters and the time is accurate to minutes. At the same time, in order to ensure the authenticity and randomness of the data as much as possible, the departure time of the order should meet the actual situation of the morning and evening peaks. Therefore, the random departure time within the corresponding time window is generated in proportion, and the number of passengers in the order is generated by a simple random method. In addition, by consulting literature and conducting research, it is proposed to define three types of scale scenarios by changing the number of orders, travel demand ratio and time window type. Each type of scale is divided into five numbers of customer points due to the different travel demand ratios. At the same time, the scenarios are further combined according to the different types of three time windows, and a total of 45 test instances can be obtained. The maximum number of customer points can reach 600, so it is a large-scale test case.

Through dynamic simulation of the test case and comparison with the path planning scheme of the company's professional dispatch customer service for manual challenge, the adaptive local search method for solving the multi-objective intercity travel vehicle path problem proposed in the present invention has a significant decrease in the four objectives, and has also significantly improved in the occupancy rate and passenger evaluation feedback. At the same time, all the solutions of the example are taken out, and the obtained target values are compared in pairs (i.e., four targets, two-by-two comparisons, for example, target f1 as the x-axis, target f2 as the y-axis). From the result diagram, the relationship between each target is roughly an inverse proportional function, indicating that there is a negative correlation between the four targets selected by this model, which verifies the correctness of the target selection of the multi-objective intercity travel vehicle path problem model established by the present invention. In addition, in order to further verify the effectiveness of the proposed method, the comparative experimental results of the proposed method with the LSMOVRPTW algorithm, MOEA/D algorithm, and NSGA2 algorithm are statistically analyzed. And two indicators widely used in multi-objective optimization algorithms are adopted, namely: IGD and HV. They are used to demonstrate the convergence and diversity of the algorithm from different perspectives, among which IGD and HV are univariate indicators. The results show that the method of the present invention is significantly better than the LSMOVRPTW algorithm in terms of both IGD and HV indicators. Specifically, in terms of the IGD indicator, according to the single-question analysis of the Wilcoxon test, the method of the present invention is significantly better than the LSMOVRPTW algorithm in 40 examples, and worse than the LSMOVRPTW algorithm in 1 example. In terms of the HV indicator, the method of the present invention is significantly better than the LSMOVRPTW algorithm in 37 examples, and worse in 3 examples. Based on the multi-question analysis of the Wilcoxon test, the method of the present invention obtains R+ values higher than R- in both IGD and HV indicators. It shows that in all rwMOVRPTW examples, the method of the present invention is generally better than the comparison algorithm. At the same time, in order to intuitively demonstrate the convergence and diversity of the method of the present invention and the LSMOVRPTW algorithm, the mapping of the non-dominated solutions obtained in several representative examples on the second objective and the third objective (f ₂ -f ₃ ), the second objective and the fourth objective (f ₂ -f ₄ ) is shown. Compared with the comparison algorithm, the non-dominated solutions of the method of the present invention are more widely distributed and closer to the Pareto front. At the same time, a module comparison test is performed on the eight neighborhood operations proposed by the present invention, each local search operator is omitted respectively, and the algorithm is run 30 times. After omitting a neighborhood operation operator, the average target of each instance is reduced. It can be observed that due to the lack of any neighborhood operation operator, especially when the number of nodes of the instance increases, the performance of the method of the present invention becomes worse in terms of the target. This means that all neighborhood operation operators are very important for the algorithm proposed by the present invention. Using IGD, HV indicators, Wilcoxon test and Frediman test, it can be observed that the results after each missing neighborhood operation operator are inferior to the results before the missing, among which the influence of neighborhood operators L4, L5, L6 and L8 is more significant. In summary, the method proposed in the present invention can efficiently and intelligently handle the path planning problem of inter-city online car-hailing travel.

The present invention defines the inter-city online car-hailing route optimization problem as a multi-objective problem with four objectives, which more comprehensively and truly reflects the essence of the inter-city travel problem; constructs an initial non-dominant vehicle route plan through a time series-based initialization construction method; then, eight neighborhood operation operators designed based on the characteristics of inter-city travel, utilize the convergence of local search and the diversity of solution plans, formulate solution selection strategies and local search selection strategies, and use adaptive local search strategies to iteratively optimize the route planning plan, so as to achieve effective coordination using the potential synergy between multiple neighborhood operations, and at the same time, further improve the quality of multi-objective solutions. The effective combination of these mechanisms can not only efficiently plan the travel routes of inter-city online car-hailing, but also use multi-objective optimization methods to provide a high-quality set of planning solutions for different needs for inter-city online car-hailing services.

Embodiment 2

In order to execute the method corresponding to the above embodiment 1 to achieve corresponding functions and technical effects, a system for determining a path for an inter-city travel vehicle is provided below, and the determination system includes:

The construction module is used to construct an inter-city travel vehicle path model with the objective function of maximizing the average number of passengers per trip, minimizing the number of vehicles, minimizing the total vehicle travel distance and minimizing the total passenger waiting time, and with the vehicle passenger capacity, service quality, time constraints and safety constraints as constraints.

The acquisition module is used to obtain intercity travel orders to be traveled; the intercity travel orders to be traveled include multiple travel orders; each of the travel orders includes the number of passengers, departure time, departure location and destination point.

A solution determination module is used to determine the travel vehicles corresponding to each travel order according to the inter-city travel vehicle path model; wherein, one travel vehicle and multiple travel orders completed by the travel vehicle constitute a travel solution; multiple travel solutions constitute a travel external archive; and the travel external archive is used as the path planning solution for the inter-city order to be traveled.

Embodiment 3

An embodiment of the present invention provides an electronic device, including a memory and a processor, wherein the memory is used to store a computer program, and the processor runs the computer program to enable the electronic device to execute the inter-city travel vehicle path determination method of embodiment 1.

Optionally, the above-mentioned electronic device may be a server.

In addition, an embodiment of the present invention further provides a computer-readable storage medium storing a computer program, which, when executed by a processor, implements the inter-city travel vehicle path determination method of embodiment 1.

In this specification, each embodiment is described in a progressive manner, and each embodiment focuses on the differences from other embodiments. The same or similar parts between the embodiments can be referred to each other. For the system disclosed in the embodiment, since it corresponds to the method disclosed in the embodiment, the description is relatively simple, and the relevant parts can be referred to the method part.

This article uses specific examples to illustrate the principles and implementation methods of the present invention. The above examples are only used to help understand the method and core ideas of the present invention. At the same time, for those skilled in the art, according to the ideas of the present invention, there will be changes in the specific implementation methods and application scope. In summary, the content of this specification should not be understood as limiting the present invention.

Claims (9)

1. An inter-city travel vehicle path determining method, comprising:

Constructing an inter-city travel vehicle path model by taking the maximized average number of passengers per trip, the minimized number of vehicles, the minimized total travel distance of the vehicles and the minimized total waiting time of the passengers as objective functions and taking the vehicle passenger capacity, the service quality, the time constraint and the safety constraint as constraint conditions;

acquiring an inter-city order to be travelled; the inter-city orders to be travelled comprise a plurality of travelling orders; each travel order comprises the number of passengers, departure time, departure place and destination place;

determining travel vehicles corresponding to the travel orders according to the inter-city travel vehicle path model; wherein one travel vehicle and a plurality of travel orders completed by the travel vehicle form a travel solution; a plurality of travel solutions form a travel external archive; and taking the trip external archive as a path planning scheme of the inter-city order to be tripped.

2. The inter-city travel vehicle path determining method of claim 1, wherein the objective function is:

f ₂ ＝|M _k |

wherein the object f ₁ Representing the maximum average number of passengers per trip, M _t 、M _k Respectively represent the number of the travel t and the vehicle k, Q _t Indicating the seating rate of the stroke t, the target f ₂ Representing a minimized number of vehicles, target f ₃ Representing a minimum total travel distance of the vehicle, M _t Indicating the number of strokes t, l _t The total travel distance of the journey t is indicated,for determining whether the journey t is to be routed to the vehicle k, the target f ₄ Meaning minimizing the total waiting time of the passengers.

3. The inter-city travel vehicle path determining method according to claim 1, wherein determining a travel vehicle corresponding to each travel order according to the inter-city travel vehicle path model specifically comprises:

determining a plurality of travel waiting trips corresponding to each travel order according to the constraint conditions and the objective function; wherein each travel to be traveled includes at least one of the travel orders and each travel to be traveled satisfies the constraint condition and the objective function;

determining vehicles corresponding to the travel routes to be traveled according to the constraint conditions and the objective function; wherein one of the vehicles and a plurality of the travel routes to be traveled completed by the vehicle form a solution; a plurality of said solutions constitute an external archive;

applying a neighborhood operator to each solution to obtain a search result corresponding to each solution;

and applying epsilon-dominant archive update strategies to each solution and the search results corresponding to each solution to obtain the travel external archive.

4. The inter-city travel vehicle path determining method according to claim 3, wherein determining a plurality of travel routes to be traveled corresponding to each of the travel orders according to the constraint condition and the objective function, specifically comprises:

taking the travel order with the earliest departure time in the preprocessing order set as a reference order of an initial journey; the initial journey at least comprises one travel order; the preprocessing order set comprises a plurality of travel orders with the same departure place;

selecting a preset pre-processing order from the to-be-processed order set, and adding the preset pre-processing order into the initial journey to obtain an updated initial journey and an order queue; the to-be-processed order set is the rest order after the reference order is removed from the pre-processing order set; the order queue is the rest order after one preset pre-processing order is removed from the to-be-processed order set;

judging whether the updated initial travel meets the constraint condition or not;

when the updated initial journey does not meet the constraint condition, deleting the preset pre-processing order from the updated initial journey, and returning to the step of selecting one preset pre-processing order from the to-be-processed order set to be added into the initial journey to obtain an updated initial journey and an order queue, and continuing to execute;

When the updated initial journey meets the constraint condition, judging whether the number of passengers in the updated initial journey reaches the passenger capacity of the vehicle;

when the number of passengers in the updated initial journey reaches the passenger capacity of the vehicle, the updated initial journey is used as a final initial journey, and travel orders in the final initial journey are deleted from the preprocessing order set, so that an updated preprocessing order set is obtained;

when the number of passengers in the updated initial journey does not reach the passenger capacity of the vehicle, judging whether the number of travel orders in the order queue is 0;

when the number of the travel orders in the order queue is not 0, the order queue is used as an order set to be processed, and a step of selecting a preset pre-processing order from the order set to be processed and adding the preset pre-processing order into the initial journey is returned to obtain an updated initial journey and the order queue;

when the number of the travel orders in the order queue is 0, returning to the step of taking the updated initial journey as the final initial journey, and deleting the travel orders in the final initial journey from the preprocessing order set to obtain an updated preprocessing order set;

When the number of the travel orders in the updated pretreatment order set is not 0, the updated pretreatment order set is used as a pretreatment order set, and the step of continuously executing the travel order with the earliest departure time in the pretreatment order set as a reference order of an initial journey is returned;

and when the number of the updated pre-processing order sets for the travel orders is 0, determining the final initial travel as a plurality of travel waiting travels corresponding to the travel orders.

5. The inter-city travel vehicle path determining method according to claim 3, wherein determining vehicles corresponding to each of the travel routes to be traveled according to the constraint condition and the objective function, specifically comprises:

taking the travel route to be traveled with the earliest departure time in the preprocessing route set as a reference route of the vehicle; the vehicle at least comprises one travel route to be traveled; the pretreatment travel set comprises a plurality of travel to be performed travel routes with the same departure place;

selecting a preset pretreatment travel from the travel set to be treated, and adding the preset pretreatment travel set to the vehicle to obtain an updated vehicle and travel queue; the stroke set to be processed is the rest stroke of the preprocessing stroke set after the reference stroke is removed; the stroke queue is the residual stroke after one preset pretreatment stroke is removed from the to-be-treated stroke set;

Judging whether the updated vehicle meets the constraint condition or not;

when the updated vehicle does not meet the constraint condition, deleting the preset pretreatment travel from the updated vehicle, and returning to the step of selecting one preset pretreatment travel from the to-be-treated travel set to be added into the vehicle to obtain an updated vehicle and a travel queue, and continuously executing;

when the updated vehicle meets the constraint condition, the updated vehicle is used as a final vehicle, and the travel route to be traveled in the final vehicle is deleted from the pretreatment route set, so that an updated pretreatment route set is obtained;

judging whether the number of travel strokes to be performed in the stroke queue is 0;

when the number of travel routes to be traveled in the route queue is not 0, the route queue is used as a route set to be processed, and a step of selecting a preset pretreatment route from the route set to be processed and adding the preset pretreatment route into the vehicle is returned to obtain an updated vehicle and route queue;

when the number of travel routes to be traveled in the route queue is 0, returning to the step of selecting a preset pretreatment route from the travel route set to be treated and adding the preset pretreatment route into the initial route to obtain an updated vehicle and route queue;

Judging whether the number of travel routes to be traveled in the updated pretreatment route set is 0;

when the number of travel routes to be traveled in the updated pretreatment route set is not 0, the updated pretreatment route set is used as a pretreatment route set, and the step of continuously executing the travel route to be traveled with the earliest departure time in the pretreatment route set as a reference route of the vehicle is returned;

and when the number of the travel routes to be traveled in the updated pretreatment route set is 0, determining that the final vehicle is a plurality of travel routes to be traveled corresponding to each travel route to be traveled.

6. The method for determining an inter-city travel vehicle path according to claim 1, wherein applying a neighborhood operator to each solution to obtain a search result corresponding to each solution, comprises:

searching each solution by applying a plurality of neighborhood operators to obtain a plurality of initial search results corresponding to each solution;

calculating the lifting degree corresponding to each solution according to a plurality of initial search results;

when the searching times are smaller than the preset times, returning to the step of applying a neighborhood operator to the preset solutions in the solutions to obtain initial searching results, and continuing to execute the steps;

When the searching times are greater than or equal to preset times, calculating an improved crowding distance of each solution according to each solution and the initial searching result corresponding to each solution;

normalizing the improved crowding distance of each solution to obtain the solution selection probability of each solution;

determining the operation selection probability of each neighborhood operator according to the lifting degree corresponding to each solution;

selecting a solution to be processed from a plurality of solutions according to the solution selection probability;

determining target neighborhood operation from a plurality of neighborhood operation operators according to the operation selection probability;

applying the target neighborhood operation to perform local search on the solution to be processed to obtain a final search result corresponding to the solution to be processed;

and updating the initial search result according to the final search result to obtain the search result corresponding to each solution.

7. An intercity travel vehicle path determination system, the determination system comprising:

the construction module is used for constructing an inter-city travel vehicle path model by taking the maximized average number of passengers per trip, the minimized number of vehicles, the minimized total running distance of the vehicles and the minimized total waiting time of the passengers as objective functions and taking the vehicle passenger capacity, the service quality, the time constraint and the safety constraint as constraint conditions;

The acquisition module is used for acquiring an inter-city order to be travelled; the inter-city orders to be travelled comprise a plurality of travelling orders; each travel order comprises the number of passengers, departure time, departure place and destination place;

the scheme determining module is used for determining the travel vehicles corresponding to the travel orders according to the inter-city travel vehicle path model; wherein one travel vehicle and a plurality of travel orders completed by the travel vehicle form a travel solution; a plurality of travel solutions form a travel external archive; and taking the trip external archive as a path planning scheme of the inter-city order to be tripped.

8. An electronic device comprising a memory for storing a computer program and a processor that runs the computer program to cause the electronic device to perform the inter-urban travel vehicle path determination method according to any one of claims 1 to 6.

9. A computer-readable storage medium, characterized in that it stores a computer program which, when executed by a processor, implements the inter-urban travel vehicle path determination method according to any one of claims 1 to 6.