Method for route optimization for demand responsive transportation

• US 10,643,478 B2
• Filed: 03/14/2018
• Issued: 05/05/2020
• Est. Priority Date: 03/15/2017
• Status: Active Grant

• Current Assignee: NEC Corporation
• Original Assignee: NEC Corporation
• Inventors: Gkiotsalitis, Konstantinos, Wu, Zongxiang, Cats, Oded
• Primary Examiner(s): Jos, Basil T.
• Application Number:
  US15/920,645
• Publication Number:
  US 20180268705A1
• Time in Patent Office: 783 Days
• CPC Class Codes: G06F 16/90335 Query processing
• CPC Class Codes: G08G 1/202 Dispatching vehicles on the basis of a location, e.g. taxi dispatching

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 multi-start sequential genetic search using a first population to identify a first solution; generating, using the first solution, a second population; performing a second multi-start genetic search using the second population to identify a second solution; and dispatching vehicles to different routes and lines according to the second solution.

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 multi-start sequential genetic search using a first population to identify a first solution;

generating, using the first solution, a second population;

performing a second multi-start genetic search using the second population to identify a second solution; and

dispatching vehicles to different routes and lines according to the second solution.

2. The method according to claim 1, further comprising generating the first population.

3. The method according to claim 2, wherein generating the first population comprises:

providing a set of first parents, each first parent having a number of elements equal to a combined number of the original service lines and the virtual service lines of the transportation network; and

randomly assigning, to each element of each first parent, a number of vehicles,

wherein the number of vehicles is selected from an admissible set of integers.

4. The method according to claim 3, wherein performing the multi-start sequential genetic search includes selecting a pair of first parents and performing, on an element-by-element basis, crossovers from one of the pair of first parent to a second of the pair of first parents.

5. The method according to claim 3, wherein performing the multi-start sequential genetic search includes selecting a pair of first parents, comparing penalty scores of the pair of first parents so as to determine a worst performing parent, and randomly replacing one or more numbers of vehicles assigned to one or more elements of the worst performing parent with one or more numbers of vehicles selected from the admissible set of integers.

6. The method according to claim 1, wherein the first solution includes a number of elements equal to a combined number of the original service lines and the virtual service lines of the transportation network.

7. The method according to claim 6, wherein each respective element of the first solution specifies a number of vehicles to assign to an original service line or a virtual service line that corresponds to the respective element.

8. The method according to claim 6, wherein generating, using the first solution, the second population comprises:

dividing the elements of the first solution into a number of subdivisions;

determining, for each respective subdivision, a number of allocated vehicles a sum of values of respective elements of the respective subdivision;

providing a set of second parents, each second parent having the number of elements equal to the combined number of the original service lines and the virtual service lines of the transportation network and the number of subdivisions;

randomly assigning, to each element of each second parent, a number of vehicles such that the number of vehicles assigned to each subdivision of each second parent is equal to the number of vehicles allocated to a corresponding subdivision of the first solution.

9. The method according to claim 8, wherein performing the second multi-start genetic search comprises selecting a pair of second parents and performing, on a subdivision-by-subdivision basis, crossovers from one of the pair of second parents to a second of the pair of second parents to form, after each replacement, an offspring.

10. The method according to claim 9, wherein after each replacement, a penalty score of the offspring is calculated.

11. The method according to claim 10, wherein an offspring with the lowest calculated penalty score is used to replace one of the pair of second parents that has a higher penalty score.

12. The method according to claim 1, wherein the second solution includes a number of elements equal to a combined number of the original service lines and the virtual service lines of the transportation network.

13. The method according to claim 12, wherein each respective element of the second solution specifies a number of vehicles to allocate to an original line or a virtual line that corresponds to the respective element.

14. The method according to claim 13, wherein dispatching vehicles to different routes and lines according to the second solution comprises allocating, to each original line and to each virtual line, the number of vehicles specified by the second solution.

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 processor-executable instructions stored at a processor-readable 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 multi-start sequential genetic search using a first population to identify a first solution;

generating, using the first solution, a second population;

performing a second multi-start genetic search using the second population to identify a second solution; and

dispatching vehicles to different routes and lines according to the second solution.