System and method of multi-objective optimization for transportation arrangement

• US 10,223,649 B2
• Filed: 10/16/2015
• Issued: 03/05/2019
• Est. Priority Date: 10/16/2015
• Status: Active Grant

• Current Assignee: SAP SE
• Original Assignee: SAP SE
• Inventors: Cheng, Yu, Li, Wen-Syan
• Primary Examiner(s): Holmes, Michael B
• Application Number:
  US14/884,773
• Publication Number:
  US 20170109631A1
• Time in Patent Office: 1,236 Days
• Field of Search: 706 46
• CPC Class Codes: G06Q 10/047 Optimisation of routes or paths, e.g. travelling salesman problem

Abstract

A technology for multi-objective optimization is provided. In accordance with one aspect, historical data and real-time data of a network of interest are provided in an integrated database. User input containing a problem to be solved and user preference for solving the problem is received. An optimization function is identified for generating at least one solution to the problem. The optimization function is identified based on the user preference. In response to identifying a single objective optimization function, the optimization function is initiated from a single objective optimization function library. In response to identifying a multi-objective optimization function, the optimization function is initiated from a multi-objective optimization function library. The optimization function retrieves the historical and real-time data based on the user preference for solving the problem. A result comprising at least one solution to the problem is provided.

Claims

1. A multi-objective optimization system, comprising:

a non-transitory memory device for storing computer-readable program code; and

a processor in communication with the memory device, the processor being operative with the computer-readable program code to;

provide, by an integrated database, historical data and real-time data of a network of interest, the real-time data comprising real-time traffic data, the real-time traffic data comprising a flow speed associated with a route;

receive, via an API call invoked by an application associated with a client device, user input comprising a transportation arrangement problem to be solved and user preference for solving the problem, the user preference having been received via a user interface of the application and comprising multiple objectives and performance parameters for weighting the objectives;

identify an optimization function for generating at least one solution to the problem, wherein the optimization function is identified based on the user preference;

in response to identifying a single objective optimization function, initiate the optimization function from a single objective optimization function library in the optimization system;

in response to identifying a multi-objective optimization function, initiate the optimization function from a multi-objective optimization function library in the optimization system;

the optimization function retrieves the historical and real-time data based on the user preference for solving the problem and generates one or more best routes for the transportation arrangement problem, wherein retrieving the historical data comprises generating an aggregation query corresponding to the optimization function and executing the aggregation query on the historical data of the integrated database, and

providing results comprising the at least one solution to the problem.

2. The system of claim 1 wherein the single objective optimization function library comprises a Linear Programming function, a Mixed Integer Programming function, a Dynamic Programming function or a combination thereof.

3. The system of claim 2 wherein the multi-objective optimization function library comprises a Skyline algorithm, a non-dominated Genetic Algorithm II, or a combination thereof.

4. The system of claim 1 wherein the optimization function is a genetic function that uses ε

-dominance in the optimization process for updating solutions to generate multiple solutions of best routes.

5. The system of claim 4 wherein the genetic function performs a crossover operation to generate new routes for evaluation and replace existing routes in response to determining that the new routes dominate the existing routes.

6. The system of claim 1 further comprising providing, by the database, a network graph of an area of interest for the transportation arrangement problem, wherein the network graph comprises nodes representing destinations of interest, and edges connecting the nodes, wherein the edges are associated with cost vectors.

7. The system of claim 6 wherein the cost vectors comprises minimal distance, minimal cost, minimal lost spoilage or a combination thereof.

8. A computer-implemented method of multi-objective optimization for transportation arrangement, comprising:

providing, by a database, historical data and real-time data of a geographical area of interest, the real-time data comprising real-time traffic data, the real-time traffic data comprising a flow speed associated with a route;

receiving, via an API call invoked by an application associated with a client device, user input comprising a transportation arrangement problem to be solved and user preference for solving the problem, the user preference having been received via a user interface of the application and comprising preference parameters for weighting multiple objectives of the transportation arrangement problem;

identifying an optimization function for generating at least one solution to the problem, wherein the optimization function is determined based on the user preference;

in response to identifying the optimization function, initiating the optimization function from one of a first optimization function library and a second optimization function library, wherein the first and second optimization function libraries are different types of optimization function libraries in an optimization system;

the optimization function retrieves the historical and real-time data based on the user preference for solving the transportation arrangement problem, wherein retrieving the historical data comprises generating an aggregation query corresponding to the optimization function and executing the aggregation query on the historical data in the database; and

providing results comprising the at least one solution of best routes.

9. The method of claim 8 wherein the first optimization function library is a single objective optimization function library comprising functions for performing single objective optimization.

10. The method of claim 9 wherein the first optimization function library comprises a Skyline algorithm, a non-dominated Genetic Algorithm II, or a combination thereof.

11. The method of claim 8 wherein the second optimization function library is a multi-objective optimization function library comprising functions for performing multi-objective optimization.

12. The method of claim 11 wherein the second optimization function library comprises a Skyline algorithm, a non-dominated Genetic Algorithm II, or a combination thereof.

13. The method of claim 12 wherein the optimization function is a genetic function that uses ε

-dominance in the optimization process for updating solutions to generate multiple solutions of best routes.

14. A non-transitory computer readable medium embodying a program of instructions executable by machine to perform steps comprising:

providing historical data and real-time data of a geographical area of interest, the real-time data comprising real-time traffic data, the real-time traffic data comprising a flow speed associated with a route;

receiving, via an API call invoked by an application associated with a client device, user input comprising a problem to be solved and user preference for solving the problem, the user preference having been received via a user interface of the application and comprising preference parameters for weighting multiple objectives of the problem;

identifying an optimization function for generating at least one solution to the problem, wherein the optimization function is determined based on the user preference;

in response to identifying the optimization function, initiating the optimization function from one of a first optimization function library and a second optimization function library, wherein the first and second optimization function libraries are different types of optimization function libraries in an optimization system;

the optimization function retrieves the historical and real-time data based on the user preference for solving the problem, wherein retrieving the historical data comprises generating an aggregation query corresponding to the optimization function and executing the aggregation query on the historical data; and

providing results comprising the at least one solution.

15. The non-transitory computer readable medium of claim 14 wherein the first optimization function library is a single objective optimization function library comprising functions for performing single objective optimization.

16. The non-transitory computer readable medium of claim 15 wherein the second optimization function library is a multi-objective optimization function library comprising functions for performing multi-objective optimization.