Vehicle dispatching method and system

• US 8,626,565 B2
• Filed: 06/30/2008
• Issued: 01/07/2014
• Est. Priority Date: 06/30/2008
• Status: Active Grant

• Current Assignee: Autonomous Solutions, Inc.
• Original Assignee: Autonomous Solutions, Inc.
• Inventors: Petroff, Thomas M.
• Primary Examiner(s): Chen, George
• Application Number:
  US12/164,740
• Publication Number:
  US 20090327011A1
• Time in Patent Office: 2,017 Days
• Field of Search: 705/1.1, 705 711- 742, 705/5, 705330-342, 705400-418
• US Class Current: 705/7.35
• CPC Class Codes: G01C 21/343 Calculating itineraries, i.e. routes leading from a starting point to a series of categorical destinations using a global route restraint, round trips, touristic trips travelling salesman problem G06Q10/04; optimisation of routes G06Q10/047
• CPC Class Codes: G01C 21/3492 employing speed data or traffic data, e.g. real-time or historical traffic control systems for road vehicles involving transmission of navigation instructions to the vehicle G08G1/0968
• CPC Class Codes: G05D 1/0088 characterized by the autonomous decision making process, e.g. artificial intelligence, predefined behaviours using knowledge based models G06N5/00
• CPC Class Codes: G05D 1/0221 involving a learning process
• CPC Class Codes: G05D 1/0291 Fleet control monitoring fleets in traffic control systems for road vehicles G08G1/127, G08G1/127
• CPC Class Codes: G06N 20/00 Machine learning
• CPC Class Codes: G06Q 10/02 Reservations, e.g. for tickets, services or events
• CPC Class Codes: G06Q 10/04 Forecasting or optimisation specially adapted for administrative or management purposes, e.g. linear programming or "cutting stock problem" market predictions or forecasting for commercial activities G06Q30/0202
• CPC Class Codes: G06Q 10/06312 Adjustment or analysis of established resource schedule, e.g. resource or task levelling, or dynamic rescheduling
• CPC Class Codes: G06Q 10/08 Logistics, e.g. warehousing, loading or distribution; Inventory or stock management
• CPC Class Codes: G06Q 2240/00 Transportation facility access, e.g. fares, tolls or parking
• CPC Class Codes: G06Q 50/28 Logistics, e.g. warehousing, loading, distribution or shipping
• CPC Class Codes: G06Q 50/30 Transportation; Communications
• CPC Class Codes: G06Q 50/40 Business processes related to the transportation industry shipping G06Q10/083
• CPC Class Codes: G08G 1/00 Traffic control systems for road vehicles arrangement of road signs or traffic signals E01F9/00 ; automatic vehicle control B62D
• CPC Class Codes: G08G 1/202 Dispatching vehicles on the basis of a location, e.g. taxi dispatching
• CPC Class Codes: G08G 1/22 Platooning, i.e. convoy of communicating vehicles

Abstract

A system and method for dispatching a plurality of vehicles operating in a work area among a plurality of destination locations and a plurality of source locations includes implementing linear programming that takes in an optimization function and constraints to generate an optimum schedule for optimum production, utilizing a reinforcement learning algorithm that takes in the schedule as input and cycles through possible environmental states that could occur within the schedule by choosing one possible action for each possible environmental state and by observing the reward obtained by taking the action at each possible environmental state, developing a policy for each possible environmental state, and providing instructions to follow an action associated with the policy.

Claims

1. A method of optimizing vehicle dispatching in a dynamic work area resulting from a linear program comprising:

inputting a vehicle dispatching schedule for a plurality of vehicles as a state representation into a reinforcement learning algorithm, the state representation having a plurality of states, each state having a plurality of possible actions;

using a computer, the computer comprising computer readable media programmed with a set of instructions causing the computer to perform the steps of;

running a simulation of the states by selecting one of the possible actions within each state, one running of the simulation being an episode and producing a result based on a proximity to optimum performance of the plurality of vehicles;

assigning a reward value based on the result;

propagating the reward value back through the simulation with reference to time between states;

for each action in each state within the episode, determining a policy value based on at least one of the reward value, a subsequent state, a subsequent action, elapsed time in the episode at the state and elapsed time in the episode at the subsequent state;

developing a policy for each state in which the action in each state that produces a maximum policy value is a preferred action;

dispatching the preferred action to the plurality of vehicles in the dynamic work area; and

causing the plurality of vehicles to perform in accordance with the preferred action.

2. The method of claim 1, wherein the dispatching the preferred action to the plurality of vehicles includes dispatching the preferred action for the state that has characteristics resembling those of the dynamic work area.

3. The method of claim 2, wherein the characteristics include locations of the plurality of vehicles in the dynamic work area, capacity at a source location, or capacity at a destination location.

4. The method of claim 1, wherein the reward value is based on the difference between tons hauled during the episode and the total tons possible declared by the linear program.

5. The method of claim 1, wherein the dispatching the preferred action occurs continuously.