Method for route optimization for demand responsive transportation

0Associated
Cases 
0Associated
Defendants 
0Accused
Products 
0Forward
Citations 
0
Petitions 
5
Assignments
First Claim
1. A method for automatically allocating a plurality of available vehicles to a plurality of original service lines and virtual service lines of a transportation network, the method comprising:
 receiving the virtual lines from a virtual line generator;
approximating a constrained fleet allocation problem with an unconstrained fleet allocation problem that utilizes penalty terms to penalize violation of constraints;
performing a multistart sequential genetic search using a first population to identify a first solution;
generating, using the first solution, a second population;
performing a second multistart genetic search using the second population to identify a second solution; and
dispatching vehicles to different routes and lines according to the second solution.
5 Assignments
0 Petitions
Accused Products
Abstract
A method for automatically allocating a plurality of available vehicles to a plurality of original service lines and virtual service lines of a transportation network includes receiving the virtual lines from a virtual line generator; approximating a constrained fleet allocation problem with an unconstrained fleet allocation problem that utilizes penalty terms to penalize violation of constraints; performing a multistart sequential genetic search using a first population to identify a first solution; generating, using the first solution, a second population; performing a second multistart genetic search using the second population to identify a second solution; and dispatching vehicles to different routes and lines according to the second solution.
1 Citation
No References
VEHICLE FLEET ROUTING SYSTEM  
Patent #
US 20130339266A1
Filed 06/14/2013

Current Assignee
Verizon Patent and Licensing Incorporated

Sponsoring Entity
Telogis Incorporated

15 Claims
 1. A method for automatically allocating a plurality of available vehicles to a plurality of original service lines and virtual service lines of a transportation network, the method comprising:
receiving the virtual lines from a virtual line generator; approximating a constrained fleet allocation problem with an unconstrained fleet allocation problem that utilizes penalty terms to penalize violation of constraints; performing a multistart sequential genetic search using a first population to identify a first solution; generating, using the first solution, a second population; performing a second multistart genetic search using the second population to identify a second solution; and dispatching vehicles to different routes and lines according to the second solution.  View Dependent Claims (2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14)
 15. A fleet dispatcher for automatically allocating a plurality of available vehicles to a plurality of original service lines and virtual service lines of a transportation network, the system comprising:
a processor configured to execute processorexecutable instructions stored at a processorreadable memory for; receiving the virtual service lines; approximating a constrained fleet allocation problem with an unconstrained fleet allocation problem that utilizes penalty terms to penalize violation of constraints; performing a multistart sequential genetic search using a first population to identify a first solution; generating, using the first solution, a second population; performing a second multistart genetic search using the second population to identify a second solution; and dispatching vehicles to different routes and lines according to the second solution.
1 Specification
Priority is claimed to U.S. Provisional Patent Application No. 62/471,474, filed on Mar. 15, 2017, the entire disclosure of which is hereby incorporated by reference herein.
The present invention relates to transportation services, and more specifically, to improving the efficiency of transportation services that serve a number of stops.
One of the most common characteristics of transportation services is the serving of a series of predefined points, for example, train stops, bus stops, and goods delivery and pickup points. Such a series of predefined points constitutes a service line with a specific origin and destination. Many transportation services have this characteristic, i.e. each vehicle serves a predetermined set of sequential points, e.g. in both directions. For instance, a tram line serves a number of predefined tram stops between an origin terminal and a destination terminal and back.
Several studies have developed methods for allocating an optimal amount of resources (e.g., an optimal number of vehicles) to each service line of a broader transportation network (e.g., a network of bus lines in a city, a network of tram lines in a city, a network of logistic lines within a pickup and delivery area) in a demandresponsive manner. Such studies include Gkiotsalitis et al. (K. Gkiotsalitis and O. Cats; Exact Optimization of Bus Frequency Settings Considering Demand and Trip Time Variations; 96th Transportation Research Board Annual Meeting, Paper No. 1701871; January 2017) and IbarraRojas et al. (O. IbarraRojas, F. Delgado, R. Giesen, and J. Muñoz; Planning, operation, and control of bus transport systems: A literature review; Transportation Research Part B: Methodological, Vol. 77, 2015, pp. 3875). The common objective of the vehicle/fleet allocation to lines is to simultaneously meet demand and limit operational costs given the constraint of resource limitations, e.g. a size of an available vehicle fleet. In those studies, the total number of available vehicles is distributed to different lines via a centralized optimization approach in order to satisfy demand at the linelevel while limiting operational costs.
Additional previous work has focused on dividing the vehicle/fleet allocation problem into two stages, wherein all vehicles are preallocated at the line level during a first stage and minor adjustments are performed during a second stage by modifying routes for a small portion of the preallocated vehicles. Previous work has also utilized offline historical demand data between point couples to create additional fixed lines that cover only the specifically observed demand patterns. Such previous work includes, e.g., Verbas et al. (I. Verbas, C. Frei, H. Mahmassani, and R. Chan; Stretching resources: sensitivity of optimal bus frequency allocation to stoplevel demand elasticities; Public Transport, Vol. 7, No. 1, 2015, pp. 120) and Verbas et al. (I. Verbas and H. Mahmassani, Optimal Allocation of Service Frequencies over Transit Network Routes and Time Periods: Formulation, Solution, and Implementation Using Bus Route Patterns; Transportation Research Record: Journal of the Transportation Research Board, 9 No. 2334, 2013, pp. 5059).
According to an embodiment, a method is described for automatically allocating a plurality of available vehicles to a plurality of original service lines and virtual service lines of a transportation network. The method includes receiving the virtual lines from a virtual line generator; approximating a constrained fleet allocation problem with an unconstrained fleet allocation problem that utilizes penalty terms to penalize violation of constraints; performing a multistart sequential genetic search using a first population to identify a first solution; generating, using the first solution, a second population; performing a second multistart genetic search using the second population to identify a second solution; and dispatching vehicles to different routes and lines according to the second solution.
The present invention will be described in even greater detail below based on the exemplary figures. The invention is not limited to the exemplary embodiments. All features described and/or illustrated herein can be used alone or combined in different combinations in embodiments of the invention. The features and advantages of various embodiments of the present invention will become apparent by reading the following detailed description with reference to the attached drawings which illustrate the following:
In performing vehicle/fleet allocation, satisfying demand at the linelevel may not provide an optimal utilization of vehicles. For instance, because different sections of a service line may exhibit significant demand variation over time, a set of points within the line may experience high demand while another set of points within the line experiences low demand. Therefore, allocating the same number of vehicles to all section of the line can result in significant vehicle underutilization within sections of the line that experience lower demand relative to higher demand sections. Furthermore, because different service directions of a service line exhibit significant demand variation over time, allocating the same number of vehicles to all service directions of the line can result in significant vehicle underutilization in the service directions that experience lower demand relative to higher demand directions.
Therefore, optimizing the fleet allocation at the linelevel is not sufficient to maximize fleet utilization. Instead, maximizing fleet utilization requires providing a more flexible scheme where vehicles are allowed to serve subparts of service lines while such subparts maintain the characteristics of the original lines e.g., the points to be traversed and the sequence in which they are traversed. However, due to the sheer volume of points to be traversed, there are a vast number of service line sections, i.e. service sublines, that can be generated by combining such points to be traversed into service sublines. Consideration of all potential service sublines that can be generated injects substantial complexity into the technical problem of fleet allocation. For instance, the technical problem of fleet allocation on a network with five fixed lines where at each line the range of allocated vehicles can be from 0 to 30 requires 30^{5 }computation iterations. If all potential subline combinations are considered and we end up with 50 new lines, this requires 30^{50}˜+∞ computation iterations for evaluating each possible fleet allocation scenario. This exponential growth of the computational complexity of the fleet allocation problem when potential sublines are considered hinders the operation of a demandresponsive route optimization where (a) new sublines are introduced onthefly and (b) the original lines are readjusted for matching the demand changes over time across the service network. In addition, fixed lines allow only the allocation of vehicles within those lines and the vehicle operator does not have the option to choose between different line formations that can match the demand in an improved manner or improve practicality of the operations.
Given the practical and computational complexity resulting from the vast number of potential service sublines, previous work has not considered allocating vehicles to potential sublines. Instead, prior work has focused primarily on generating fixed lines based on demand patterns in an offline manner because of the substantial computational complexity required for evaluating all potential sublines that can be generated in a study area and allocating vehicles to those sublines. Embodiments of the present invention improve the allocation of transportation resources, e.g. vehicles, within transportation networks by providing novel systems and methods for considering potential service sublines during said allocation of transportation resources. Embodiments of the present invention thereby provide for improvements in transportation network operation by increasing operational efficiency through the reduction of operational costs required to satisfy demand at service points throughout the network.
Service lines in a transportation network often start from an origin point, serve a predefined number of points (stops), reach a final destination point, and then return to the origin. Improving the efficiency of such service lines is a multiobjective optimization problem with two conflicting priorities: (i) satisfying demand at each point (stop), and (ii) reducing operational costs. Embodiments of the present invention provide novel systems and methods that employ a multistart sequential genetic search in solving the computationally intractable problem of vehicle allocation to service lines and sublines given a set of practical and operational constraints. Specifically, systems and methods according to embodiments of the invention (a) perform a genetic search in which all elements of a genotype are checked onebyone in a sequential manner, (b) aggressively replace the worst parent of a couple with newly generated offspring at each iteration in order to rapidly identify an optimal solution, and (c) utilize multiple parents (more than two) in order to explore a solution space from multiple starting points and avoid local optimum traps.
Embodiments of the present invention provide systems and methods that utilize one or more genetic searches that employ crossovers between genotypes of members of a population at different levels of granularity, e.g. sequential crossovers at the smallest unit of the genetype and tailored crossovers at a larger unit of the genotype (the larger units including multiple one of the smallest unit). Specifically, systems and methods are described herein that evaluate a penalty function of an allocation profile at a scale of the larger unit and allow the presence of some elements that, at the scale of the smallest unit, deteriorate the penalty function score if the combination of all the elements returns a penalty function improvement at the scale of the large unit.
Embodiments of the present invention provide systems and methods that generate and utilize virtual lines that represent segments of physical service lines, i.e. service sublines, for onestage optimization of a demandresponsive automated fleet allocation problem.
A Method is described herein for automatically allocating a fleet of vehicles to one or more service lines and sublines of a transportation network. The method includes generating virtual lines utilizing an input database, approximating a problem of allocating vehicles to the service lines and sublines while subject to certain constraints with an unconstrained vehicle allocation problem that utilizes penalty terms to penalize the violation of constraints, rapidly exploring the vast solution space with a multistart sequential genetic search in order to find an approximate global optimal solution, utilizing the approximate global optimal solution to form a new population for a second genetic search, performing the second genetic search during which tailored crossovers are performed, and dispatching vehicles into different routes and lines based on the results of the second genetic search. The aforementioned method can be reapplied in a demandresponsive manner (e.g., when spatiotemporal demand changes significantly).
Systems and methods for automatically generating new “virtual lines,” which are part of a set of “original lines,” and adjusting the number of vehicles allocated to the new virtual lines in order to satisfy a timevarying demand is described herein. The term “vehicle” as used herein can refer to various mobile entities capable of serving a series of demand points, e.g. cars, trucks, drones, robots, etc. The term “original lines” can be used to refer to predefined physical service lines that exist in a transportation service network or computerized representations thereof. The term “virtual lines” can be used to refer to segments, or subparts, or the predefined physical service lines, i.e. service sublines that serve only certain segments of the original lines.
The demandresponsive automated fleet dispatching system further includes a DemandResponsive Automated Fleet Dispatcher (DRAFD) 102 configured to allocate vehicles to different lines (both original and virtual ones) and a Virtual Line Generator (VLG) 103 configured to divide representations of the complete physical service lines, i.e. the original lines, into potential service sublines, or virtual lines. Each of the DRAFD 102 and the VLG 103 can be, for example, a physical machine including compute resources, storage resources, and network resources or a component thereof. Furthermore, each of the DRAFD 102 and the VLG 103 can be a virtual machine or a collection of virtual machines hosted by one or more physical machines including compute resources, storage resources, and network resources. The compute resources of the physical machines can, for example, include one or more processors each having one or more processor cores. The storage resources of the physical machines can, for example, include processor readable memory, e.g., randomaccessmemory (RAM) and/or cache memory. The network resources can include, for example, a physical network interface controller. The physical machines can store, at the storage resources thereof, a set of processor executable instructions necessary to perform the processes executed by the DRAFD 102 and the VLG 103 and configured to be executed by the processing resources thereof.
The DRAFD 102 allocates available vehicles to a mix of original lines and virtual lines of the transportation network. In order to do so, the DRAFD 102 receives information stored at the database 101 and a set of virtual lines provided by the VLG 103. Alternatively, the DRAFD 102 can generates sets of virtual lines itself, for example, by including its own virtual line generator. The allocation of available vehicles to the original lines and virtual lines can be updated every time a significant demand variation is observed. For example, in public transport systems and logistics operations, a oneday period can be split into three to six time periods within which observed demand is relatively homogeneous and the allocation of available vehicles can be updated as one such time period transitions to another. The time periods during which observed demand is relatively homogenous could be, for example, an early morning time period, a morning peak time period, a noon time period, an early afternoon time period, an afternoon peak time period, and a night time period.
The demandresponsive automated fleet dispatching system 100 additionally includes a set of vehicles 104 that can be allocated to one or more original lines and/or virtual lines of the transportation system. In performing demandresponsive automated fleet dispatching, the input database 101 provides updated spatiotemporal demand data to the DRAFD 102 at (1). At (2), the VLG 103 provides a set of virtual lines to the DRAFD 102. At (3), the DRAFD introduces ondemand virtual lines as new service lines and allocates vehicles to those lines. At (4), the DRAFD modifies the allocation of vehicles to the original lines in order to reduce operations costs through superior demand matching.
In allocating the available vehicles, the DRAFD 102 is configured to solve a fleet allocation problem. The DRAFD 102 can exhaustively generate virtual lines (or receive virtual lines from the VLG 103—which can exhaustively generate virtual lines) and does not perceive the demandresponsive fleet allocation problem as a problem of allocating resources to a static, predefined set of lines, for example a set of lines that is already predefined based on offline demand data patterns. According to embodiments of the invention, the DRAFD 102 and/or the VLG 103 generate all possible virtual lines and the DRAFD 102 performs a onestage vehicle allocation for a set of generated routes. For a time period during which observed demand can be characterized as homogeneous, embodiments of the present invention define the singlestage allocation problem as follows:
where the objective function of the optimization problem has three terms. The second term, α_{1}Σ_{l∈L}n_{l}C_{l}, denotes the operational cost in vehiclekilometers traveled where n_{l }is the number of allocated vehicles to each line l, C_{l }is the expected roundtrip travel time for each line l and α_{l }is a weighting factor. The third term α_{2}Σ_{l∈L}n_{l }is the fixed cost of utilizing one more vehicle. The first term, which is contradictory to the 2^{nd }and 3^{rd }terms, represents the demand matching level at all points of the network. The demand matching can be defined in different ways, for example, as the level of demand between different points of a line multiplied by the waiting time of demand generators such as passengers and/or goods. To explain the first term, let assume that L_{o }is the set of original lines and L the set of all lines—both virtual and original. b_{lo,i,j }is the demand between points i,j that can be served from the original service lo or any other virtual line service which is generated from the original service lo. In addition, K_{l}_{o}_{,i,j }is a function that returns the set of virtual lines that can serve the demand b_{l}_{o}_{,i,j}. Therefore, the waiting time of passengers/goods that want to move between two points i,j of the original line l_{o }is equal to the inverse of the number of vehicles allocated to all lines in K_{lo,i,j }divided by the total travel time of each of those lines.
The objective function of the optimization problem is also subject to several additional constraints. The first constraint (n_{1}, n_{2}, . . . , n_{L})∈N^{L }requires that the number of allocated vehicles to each line n_{l }is an integer value. The second constraint Σ_{l=1}^{L}n_{l}≤γ requires that the total number of allocated vehicles not exceed the maximum number of available vehicles, denoted by γ. The third constraint Σ_{l∈LL}_{o }n_{l}≤πγ requires that the total number of vehicles allocated to virtual lines not exceed the maximum number of vehicles, πγ, that can serve virtual lines for practicality reasons. The fourth constraint provides that the number of virtual lines that can be allowed to be operational is denoted with η.
The objective function is noncontinuous, fractional (nonlinear), nonconvex, and contains the secondary function K_{l}_{o}_{,i,j }which is critical for returning all virtual lines that can serve the demand between two points. This restricts the implementation of exact optimization methods and the computational complexity with simple enumeration is exponential: Z^{ρ}, where Z is an integer set from which the number of vehicles of each line is selected and ρ=Σ_{l∈L}n_{l}. Let us say that at each line can be allocated any number of vehicles from 0 to 100; then, for a set of 500 virtual lines the number of computations are 100^{500}˜+∞. Therefore, finding a globally optimal solution for the allocation of vehicles to lines via a onestage optimization is not possible with the use of stateoftheart approaches for discrete, nonconvex optimization such as simple enumeration (bruteforce).
Those penalty terms are greater than zero when the problem constraints are violated (thus, adding more cost to the original objective function) and equal to zero when all constraints are satisfied (thus, not affecting negatively the objective function score). The weights of the penalty terms, W_{1}, W_{2}, have high values such that priority is given to the satisfaction of constraints over the objective function minimization. Their values can be determined randomly with the only requirement being that they are high enough for ensuring that the violation of a constraint penalizes the objective function more than any potential increase of the objective function in order to prioritize first the satisfaction of all constraints and then shift the attention to the reduction of f(n), i.e. the objective function. This resulting penalty function, P(n), returns a different score when the decision variables n change their values, and the objective of the proposed subdivision and sequential genetic search is to find a set of vehicle allocations n* that minimizes the penalty function (approximate global optimum). Given the exponential complexity of the problem and the large set of potential solutions—(˜±∞) for real world scenarios—the problem is computationally intractable. The subdivision and sequential genetic search are employed to perform an effective search of the solution space.
At 210, a sequential genetic search is initiated using a population of initially random parents. Each parent, K_{1}, K_{2}, . . . , K_{m}, specifies an allocation of vehicles to lines. For example, for parent K_{1 }the allocation of vehicles to lines is n^{{K1}}={n_{1}^{K1}, . . . , n_{L}^{K1}} where n_{1}^{K1}, . . . , n_{L}^{K1 }are random integer numbers from the admissible set Z. This initial random allocation of vehicles for each parent K_{1 }is the genotype of the parent. For example, the initial random allocation n^{{K1}}={n_{1}^{K1}, . . . , n_{L}^{K1}} is the genotype of the parent K_{1}. During the sequential part of the genetic search, two random parents from the set K_{1}, K_{2}, . . . , K_{m }are selected as a couple and a sequential genetic search is applied to the genotypes of those two parents. For example, if the parents K_{1}, K_{3 }are randomly selected for the sequential genetic search, then the sequential genetic search is performed according to the following pseudocode:
During the sequential genetic search, the worst performing parent of the couple, for example the couple K_{1}, K_{3}, is replaced by the best offspring that results from the sequential crossover and sequential mutation. Thereafter, another couple is randomly selected and the same procedure continues until a termination criterion is met (i.e., a predetermined maximum number of iterations).
Using the sequential genetic search described above provides a number of advantages. Performing the sequential crossover and mutation increases the probability of producing better offspring and also increases the speed of the search process because the elements of each allocation are considered one by one. However, the sequential crossover and mutation also increases the chances of becoming trapped by a local optimum. Aggressive Replacement of Parents with Offspring rapidly generates new populations with improved allocations thereby moving in an aggressive direction towards the optimal solution. Utilization of multiple parents allows for exploration of the solution space from multiple starting points and thereby increases the probability of identifying a solution closer to the global optimum and of becoming trapped by a local optimum.
Further improvements to the allocation of vehicle provided by the Offspring* solution can be realized by dividing the entire set of individual original and virtual lines to which vehicles are allocated into larger groups of lines, i.e. subdivisions, and then performing a subdivision genetic search at the subdivision level at 220. During the subdivision genetic search at 220, crossovers at the subdivision level can be performed in order to increase the probability of producing better offspring. For providing an initial set of allocations for the second genetic search, the Offspring* solution with allocation n^{{Offspring*}}={n_{1}^{Offspring*}, . . . , n_{L}^{Offspring*}} can be used to generate new parents O_{1}, O_{2}, . . . , O_{m}. Then, tailored crossovers between subdivisions of the new parents can be performed during the second genetic search—and can be performed in a manner that ensures that the constraints of the initial constrained optimization problem continue to be satisfied. For example, if the parents O_{1}, O_{3 }are randomly selected for the subdivision genetic search, then the subdivision genetic search is performed according to the following pseudocode:
The subdivision genetic search continues by randomly selecting other sets of parent couples from the list O_{1}, O_{2}, . . . , O_{m }until a maximum number of allowed iterations are performed. At each iteration, the worst performing parent of the couple is replaced by the Best_{offspring }and while the subdivision crossover ensures that all constraints remain satisfied. The subdivision genetic search allows exploration of different fleet allocation profiles while the penalty function is evaluated at the subdivision level (as opposed to being evaluated at the line level as in the sequential genetic search).
At 315, two parents K_{i}, K_{j }are selected at random from the list of initially random parents K_{1}, K_{2}, . . . , K_{m }and the score of each of the parents P(n^{{K}^{i}^{}}) and P(n^{{K}^{j}^{}}) is calculated using the penalty function provided by the unconstrained vehicle allocation optimization problem. If P(n^{{K}^{i}^{}})≤P(n^{{K}^{j}^{}}), then the process sets Offspring=n^{{K}^{i}^{}} and Best_{Offspring}=n^{{K}^{i}^{}}. Otherwise, the process sets Offspring=n^{{K}^{j}^{}} and Best_{Offspring}=n^{{K}^{j}^{}}).
At 320, the process initializes a second counter value to one, i.e. y=1. At 325, the process replaces, with a 50% probability, n_{y}^{Offspring }with n_{y}^{K}^{j }(where P(n^{{K}^{i}^{}})≤P(n^{{K}^{j}^{}})) or with n_{y}^{K}^{i }otherwise, and if the replacement is performed, calculates the scores P(n^{{Offspring}}) and P(n^{{Best}^{offspring}^{}}). If P(n^{{Offspring}})<P(n^{{Best}^{Offspring}^{}} the process then sets Best_{Offspring}=Offspring. At 330, the process replaces n_{y}^{Offspring }with random number from the admissible set Z and again calculates the scores P(n^{{Offspring}}) and P(n^{{Best}^{Offspring}^{}}). Once again, if P(n^{{Offspring}})<P(n^{{Best}^{Offspring}^{}} the process sets Best_{Offspring}=Offspring. At 335 the process sets Offspring=Best_{Offspring }and increments the second counter value y and then, at 340, compares the second counter value y with the total number of values in the genotype, i.e. L. If y≤L, the process returns to 325; otherwise the process proceeds to 345 where the process replaces the parent with the lower score with Best_{Offspring}.
At 350, the process increments the counter value x and then, at 355, compares the value of x with a maximum number of allowed iterations, X. If x≤X, the process returns to 315; otherwise the process proceeds to 360 where a set of Offspring O_{1}, O_{2}, . . . , O_{m }is generated. At 365, the current best solution is selected from the set of all generated Offspring O_{1}, O_{2}, . . . , O_{m }and provided as output. For example, the process can, at 365, calculate a penalty score for each of the generated Offspring O_{1}, O_{2}, . . . , O_{m}, or alternatively, can utilize a previously calculated penalty score for each of the generated Offspring. For example, such a previously calculated penalty score could be associated with the allocations at 345 and then later be recalled by the process. The solution with the lowest penalty score of all the generated Offspring O_{1}, O_{2}, . . . , O_{m}, which can be referred to as Offspring*, is then designated as the current best solution and provided as output.
By definition of the penalty function, if all constraints are satisfied from the Offspring* solution then the penalty function score P(n^{{Offspring*}}) will be equal to the objective function score f(n). Therefore, by reducing further the penalty function score the objective function score f(n) can be reduced exactly the same while assuring that all constraints remain satisfied.
At 510, the process initializes a counter value to one, i.e. x=1. At 515, two parents O_{i}, O_{j }are selected at random from the list of initially random parents O_{1}, O_{2}, . . . , O_{m }and the score of each of the parents P(n^{{O}^{i}^{}}) and P(n^{{O}^{j}^{}}) is calculated using the penalty function provided by the unconstrained vehicle allocation optimization problem. If P(n^{{O}^{i}^{}})≤P(n^{{O}^{j}^{}}), then the process sets Offspring=n^{{O}^{i}^{}} and Best_{Offspring}=n^{{O}^{i}^{}}. Otherwise, the process sets Offspring=n^{{O}^{j}^{}} and Best_{Offspring}=n^{{O}^{j}^{}}.
At 520, the process initializes a second counter value to one, i.e. y=1. At 525, the process replaces, with a 50% probability, the yth subdivision of the Offspring with the yth subdivision of O_{j }(where P(n^{{O}^{i}^{}})≤P(n^{{O}^{j}^{}})) or with the yth subdivision of O_{i }otherwise, and if the replacement is performed, calculates the scores P(n^{{offspring}}) and P(n^{{Best}^{Offspring}^{}}). If P(n^{{Offspring}})<P(n^{{Best}^{Offspring}}) the process then sets Best_{Offspring}=Offspring. At 530 the process sets Offspring=Best_{Offspring }and increments the second counter value y and then, at 535, compares the second counter value y with the total number of subdivisions, i.e. S. If y≤S, the process returns to 525; otherwise the process proceeds to 540 where the process replaces the parent with the lower score with Best_{Offspring}.
At 545, the process increments the counter value x and then, at 550, compares the value of x with a maximum number of allowed iterations, X. If x≤X, the process returns to 515; otherwise the process proceeds to 555 where a set of new Offspring O_{1}, O_{2}, . . . , O_{m }is generated. At 560, the best solution is selected from the set of all generated new Offspring O_{1}, O_{2}, . . . , O_{m }and provided as output.
Prior to performing demandresponsive fleet dispatching using any of the processes described in
Starting from the original lines, a set of virtual lines can be generated for shortturn scenarios and interlining scenarios. Not all generated virtual lines need be operational (some of them might not be operated by vehicles if they do not match the demand properly and/or have high operational costs). Therefore, there is no initial guarantee that virtual lines will be operational (this is decided during the demandresponsive fleet dispatching processes).
One process can be used to generate shortturn virtual lines while a different process can be used to generate interline virtual lines. For generating shortturn virtual lines, all points of an original line or a smaller set of significant control points of that original line can be considered as potential shortturn points. In generating short turn lines, a process can select one original service line l on which to generate shortturn related lines for tackling a demand imbalance present between different parts of that original service line. Thereafter, the process can iteratively select each of the other original service lines and generate shortturn related lines for tackling demand imbalances present between different parts of those original service lines. The shortturn related lines will be sublines of the original service line and will cover a fraction of the points covered by the original line in exactly the same sequence as those points are covered on the original line. In addition, the shortturn related lines can be required to visit either the origin point of the original line or the destination point of the original line (as those points are used as terminals where the vehicle driver can rest after the completion of each virtual line trip).
In generating short turn lines for a selected service line l, a process can select one service start point and generate a set of possible shortturn virtual lines that begin at the selected service start point and then iteratively select every other potential service start point on the selected service line l and generate sets of possible shortturn lines for each of those potential service start points. For each selected service start point, the process can select all potential break points at which the virtual line could end. The potential break points can be any other point on the original service line or some subset thereof. When generating virtual lines for a selected start point and break point of a selected original line, the process can determine whether a rest point is required for the virtual line, and if so, select a rest point from amongst possible rest points. The process can also determine whether deadhead time, i.e. time for a trip from the break point to return to the starting point with no passengers, is required for the virtual line.
In generating interline virtual lines interlining between control points of different original lines can be enabled. Although bidirectional short turn virtual lines can serve parts of original lines with excessive demand, such virtual lines do not provide a mechanism for addressing directional demand imbalances. However, circular interlining services can address directional demand imbalances by serving onedirectional demand. Therefore, circular interlining services can avoid the inefficiency that would otherwise result when additional bidirectional short turn service lines are introduced to satisfy high but directionally imbalanced demand.
In generating interline virtual lines, a process can select one original service line l on which to an interline virtual lines can originate and then iteratively select each of the other original service lines and generate interline virtual lines that originate from those original service lines. In generating interline virtual lines for a selected service line l on which the virtual lines originate, a process can select one service start point and generate a set of possible interline virtual lines that begin at the selected service start point and then iteratively select every other potential service start point on the selected service line l and generate sets of possible interline virtual lines for each of those potential service start points. For each selected service start point, the process can select all potential outgoing points at which the interline virtual line departs the selective service line l on which the virtual line originates. For each selected outgoing point, the process can consider all potential transfer points on other original service lines at which the interline virtual line could continue.
From table 1, an improvement of 25.8% was realized by allocating vehicles to virtual lines and not only at the original lines with the use of the sequential genetic search with subdivision crossover according to them embodiment of the invention. Exact optimization methods could not converge to an optimal while other SoA heuristics for discrete optimization such as Simulated Annealing could not converge due to local optimum traps which did not allow the algorithm to explore other parts of the solution space.
The sequential genetic search with subdivision crossover according to the embodiment of the invention is a heuristic approach that can return a different approximate global optimum every time it is executed. Therefore, the transport operator can get different allocations of vehicles to original and virtual lines that have almost the same effect on reducing the penalty score and select the one which is easier to implement in practice (select “the more practical allocation”). For improving the practical implementation, transport operators can set tighter constraints on the characteristics of virtual lines that can be served from their vehicles and the sequential genetic search with subdivision crossover will return solutions that satisfy those requirements due to the treatment of those constraints as penalties.
Different transport services might have a set of predetermined tactical and operational requirements that do not allow the optimal allocation of vehicles to the original and virtual lines. For instance, one transport operator that operates a number of services might have a number of additional constraints apart from the total number of available vehicles. Typical examples of those constraints can be: (1) each service line should have at most an X minute headway between consecutive vehicles for ensuring that passengers/goods do not wait more than that time; (2) vehicle drivers might prefer to operate more at the original lines because they are more experienced on those routes and at least X % of the number of available vehicles should be assigned to those lines; (3) operators might prefer to achieve a certain balance between the generated shortturn and interlining lines by setting a percentage of X % for shortturn lines and 100X % for interlinings.
Those constraints can be treated exactly like the total number of available vehicles that is presented in equation 1. For the implementation of those constraints during the optimization process where the total number of available vehicles are allocated to different original and virtual lines those constraints are introduced to the objective function with the use of penalty terms. Those penalty terms are greater than zero when the problem constraints are violated (thus, adding more cost to the original objective function of eq. 1) and equal to zero when all constraints are satisfied (thus, not affecting negatively the objective function score). The weights of the penalty terms have high values to ensure that priority is given to the satisfaction of constraints over the objective function minimization. Therefore, the constrained optimization problem of equation 1 is transformed to an approximate unconstrained one where all the constraints imposed by the transport operator are modeled as penalty terms. Therefore, by satisfying those constraints the potential of improving the demand matching and operational costs by allocating vehicles to original and virtual lines is reduced since the constraints might not permit the selection of the best option. To give a practical example, from table 1 an improvement of 25.8% was realized by allocating vehicles to virtual lines and original lines with the use of the sequential genetic search with subdivision crossover. If the transport operator though dictates that at least 80% of the vehicles should be allocated to original lines to improve the service practicability, then this improvement falls to 11.6% at this particular scenario.
While the invention has been illustrated and described in detail in the drawings and foregoing description, such illustration and description are to be considered illustrative or exemplary and not restrictive. It will be understood that changes and modifications may be made by those of ordinary skill within the scope of the following claims. In particular, the present invention covers further embodiments with any combination of features from different embodiments described above and below. Additionally, statements made herein characterizing the invention refer to an embodiment of the invention and not necessarily all embodiments.
The terms used in the claims should be construed to have the broadest reasonable interpretation consistent with the foregoing description. For example, the use of the article “a” or “the” in introducing an element should not be interpreted as being exclusive of a plurality of elements. Likewise, the recitation of “or” should be interpreted as being inclusive, such that the recitation of “A or B” is not exclusive of “A and B,” unless it is clear from the context or the foregoing description that only one of A and B is intended. Further, the recitation of “at least one of A, B and C” should be interpreted as one or more of a group of elements consisting of A, B and C, and should not be interpreted as requiring at least one of each of the listed elements A, B and C, regardless of whether A, B and C are related as categories or otherwise. Moreover, the recitation of “A, B and/or C” or “at least one of A, B or C” should be interpreted as including any singular entity from the listed elements, e.g., A, any subset from the listed elements, e.g., A and B, or the entire list of elements A, B and C.