Transporting goods using a fleet of vehicles

Patent metadata

Field	Value
Publication number	US-2017352003-A1
Application number	US-201715615054-A
Country	US
Kind code	A1
Filing date	Jun 6, 2017
Priority date	Jun 6, 2016
Publication date	Dec 7, 2017
Grant date	—

Abstract

This disclosure relates to transporting goods using a fleet of vehicles that is optimised. A processor solves a linear program to optimise a cost value by selecting one of multiple fleet configuration candidates comprising a number and type of vehicles that meet a transport demand at minimum cost. The linear program comprises constraints associated with multiple days. The processor then determines for one of the multiple days a further fleet configuration candidate based on an output of solving the linear problem and adds the further fleet configuration candidate to the multiple fleet configuration candidates by including an additional corresponding column into the linear program. The steps of solving the linear program, determining a further fleet configuration candidate and adding the further fleet configuration candidate to the multiple fleet candidates are then repeated until a termination condition is met.

First claim

1 . A transport system, the transport system comprising:
one or more sender warehouses storing goods at respective sender locations; multiple receiver warehouses for storing the goods at respective receiver locations; a data collection server to receive demand data for multiple days, convert the demand data into a data format suitable for one of multiple vehicle routing engines, and store the demand data on a datastore; a communication network to transmit the demand data from the data collection server to a processing server; a processing server to retrieve the demand data and to determine an optimised fleet configuration comprising a number and type of vehicles based on the demand data for multiple days, the processing server comprising a linear program solver and the one of multiple vehicle routing engines, the processing server being configured
to activate the linear program solver to optimise a cost value by selecting one of multiple fleet configuration candidates that meet a transport demand represented by the demand data, the linear program comprising constraints associated with multiple days;
to activate the one of multiple vehicle routing engines to determine based on the demand data in the suitable data format for one of the multiple days a further fleet configuration candidate based on an output of the linear program solver;
to add the further fleet configuration candidate to the multiple fleet configuration candidates by including an additional corresponding column into the linear program;
to repeat the steps of solving the linear program, determining a further fleet configuration candidate and adding the further fleet configuration candidate to the multiple fleet candidates until a termination condition is met; and
a fleet of vehicles according to the selected one of multiple candidate fleet configurations to transport the goods from the sender locations to the receiver locations according to the demand data.

2 . A computer implemented method for determining an optimised fleet configuration, the method comprising:
solving a linear program to optimise a cost value by selecting one of multiple fleet configuration candidates comprising a number and type of vehicles that meet a transport demand at minimum cost, the linear program comprising constraints associated with multiple days; determining for one of the multiple days a further fleet configuration candidate based on an output of solving the linear problem; adding the further fleet configuration candidate to the multiple fleet configuration candidates by including an additional corresponding column into the linear program; repeating the steps of solving the linear program, determining a further fleet configuration candidate and adding the further fleet configuration candidate to the multiple fleet candidates until a termination condition is met; and in response to the termination condition being met outputting the selected one of multiple fleet candidates as the optimised fleet configuration.

3 . The method of claim 2 , wherein the method further comprises performing column generation comprising a master problem and a sub-problem, the linear program being the master problem and determining for one of the multiple days a further fleet configuration candidate being the sub-problem.

4 . The method of claim 2 , wherein determining for one of the multiple days a further fleet configuration candidate comprises determining a fleet configuration that solves a vehicle routing problem for the one of the multiple days.

5 . The method of claim 2 , wherein determining for one of the multiple days a further fleet configuration candidate comprises determining a cost coefficient for the further fleet configuration candidate.

6 . The method of claim 5 , wherein determining the cost coefficient comprises optimising a reduced cost associated with the further fleet configuration candidate.

7 . The method of claim 5 , wherein the linear problem comprises the cost coefficient of the further fleet configuration candidate.

8 . The method of claim 2 , wherein the output of solving the linear problem is a value of a dual variable of the linear problem.

9 . The method of claim 8 , wherein the dual variable of the linear problem is indicative of the costs of the vehicles.

10 . The method of claim 2 , wherein the linear problem comprises constraints to meet the transport demand.

11 . The method of claim 2 , where the linear problem comprises a binary decision variable for each fleet configuration candidate indicative of whether that fleet configuration candidate is selected.

12 . The method of claim 2 , wherein each of the multiple fleet configuration candidates comprise a number of vehicles for each of multiple vehicle types.

13 . The method of claim 2 , wherein the linear problem comprises one or more columns associated with vehicles in a prior fleet and one or more columns associated with buying vehicles or selling vehicles or both.

14 . The method of claim 2 , wherein the linear problem comprises one or more columns associated with hiring vehicles on one or more of the multiple days.

15 . The method of claim 2 , wherein determining the further fleet configuration candidate comprises determining a routing of vehicles that meets a demand for the further fleet configuration candidate.

16 . The method of claim 15 , wherein the method further comprises determining for each route whether to buy or hire a vehicle for that route.

17 . The method of claim 15 , wherein determining the routing and repeating the step of determining a further fleet configuration candidate comprises determining multiple routings for respective fleet configuration candidates and the method further comprises selecting one of the multiple routings based on the selected one of multiple fleet candidates.

18 . The method of claim 2 , wherein determining the further fleet configuration candidate comprises performing a branch and price method.

19 . The method of claim 18 , wherein the branch and price method branches on a number of vehicles for each of multiple vehicle types.

20 . The method of claim 2 , wherein determining for one of the multiple days a further fleet configuration candidate comprises selecting the one of the multiple days based on a score for each of the multiple days.

21 . The method of claim 20 , wherein the score for each of the multiple days is based on a dual variable of the linear program.

22 . The method of claim 2 , wherein determining for one of the multiple days a further fleet configuration candidate comprises activating one of multiple routing engines.

23 . A non-transitory computer readable medium that has an executable program stored thereon that when executed causes a computer to perform the method of claim 2 .

24 . A computer system for determining an optimised fleet configuration, the computer system comprising:
an input port to receive a transport demand for each of multiple days; a processor
to solve a linear program to optimise a cost value by selecting one of multiple fleet configuration candidates comprising a number and type of vehicles that meet the transport demand, the linear program comprising constraints associated with multiple days,
to determine for one of the multiple days a further fleet configuration candidate based on an output of solving the linear problem,
to add the further fleet configuration candidate to the multiple fleet configuration

Assignees

• Nat Ict Australia Ltd

Inventors

• Bertoli Francesco
• Kilby Philip
• Urli Tommaso

Classifications

• G06Q10/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 title

• G06Q10/0875 Primary

  Itemisation or classification of parts, supplies or services, e.g. bill of materials · CPC title