A General Cooperative Optimization Approach for Distributing Service Points in Mobility Applications
This article presents a cooperative optimization approach (COA) for distributing service points for mobility applications, which generalizes and refines a previously proposed method. COA is an iterative framework for optimizing service point locations, combining an optimization component with user i...
| Main Authors: | , , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
MDPI AG
2021-08-01
|
| Series: | Algorithms |
| Subjects: | |
| Online Access: | https://www.mdpi.com/1999-4893/14/8/232 |
| _version_ | 1827686250848452608 |
|---|---|
| author | Thomas Jatschka Günther R. Raidl Tobias Rodemann |
| author_facet | Thomas Jatschka Günther R. Raidl Tobias Rodemann |
| author_sort | Thomas Jatschka |
| collection | DOAJ |
| description | This article presents a cooperative optimization approach (COA) for distributing service points for mobility applications, which generalizes and refines a previously proposed method. COA is an iterative framework for optimizing service point locations, combining an optimization component with user interaction on a large scale and a machine learning component that learns user needs and provides the objective function for the optimization. The previously proposed COA was designed for mobility applications in which single service points are sufficient for satisfying individual user demand. This framework is generalized here for applications in which the satisfaction of demand relies on the existence of two or more suitably located service stations, such as in the case of bike/car sharing systems. A new matrix factorization model is used as surrogate objective function for the optimization, allowing us to learn and exploit similar preferences among users w.r.t. service point locations. Based on this surrogate objective function, a mixed integer linear program is solved to generate an optimized solution to the problem w.r.t. the currently known user information. User interaction, refinement of the matrix factorization, and optimization are iterated. An experimental evaluation analyzes the performance of COA with special consideration of the number of user interactions required to find near optimal solutions. The algorithm is tested on artificial instances, as well as instances derived from real-world taxi data from Manhattan. Results show that the approach can effectively solve instances with hundreds of potential service point locations and thousands of users, while keeping the user interactions reasonably low. A bound on the number of user interactions required to obtain full knowledge of user preferences is derived, and results show that with 50% of performed user interactions the solutions generated by COA feature optimality gaps of only 1.45% on average. |
| first_indexed | 2024-03-10T09:05:41Z |
| format | Article |
| id | doaj.art-d81bce1431ed42509e6d634609611be1 |
| institution | Directory Open Access Journal |
| issn | 1999-4893 |
| language | English |
| last_indexed | 2024-03-10T09:05:41Z |
| publishDate | 2021-08-01 |
| publisher | MDPI AG |
| record_format | Article |
| series | Algorithms |
| spelling | doaj.art-d81bce1431ed42509e6d634609611be12023-11-22T06:27:40ZengMDPI AGAlgorithms1999-48932021-08-0114823210.3390/a14080232A General Cooperative Optimization Approach for Distributing Service Points in Mobility ApplicationsThomas Jatschka0Günther R. Raidl1Tobias Rodemann2Institute of Logic and Computation, TU Wien, 1040 Vienna, AustriaInstitute of Logic and Computation, TU Wien, 1040 Vienna, AustriaHonda Research Institute Europe, 63073 Offenbach am Main, GermanyThis article presents a cooperative optimization approach (COA) for distributing service points for mobility applications, which generalizes and refines a previously proposed method. COA is an iterative framework for optimizing service point locations, combining an optimization component with user interaction on a large scale and a machine learning component that learns user needs and provides the objective function for the optimization. The previously proposed COA was designed for mobility applications in which single service points are sufficient for satisfying individual user demand. This framework is generalized here for applications in which the satisfaction of demand relies on the existence of two or more suitably located service stations, such as in the case of bike/car sharing systems. A new matrix factorization model is used as surrogate objective function for the optimization, allowing us to learn and exploit similar preferences among users w.r.t. service point locations. Based on this surrogate objective function, a mixed integer linear program is solved to generate an optimized solution to the problem w.r.t. the currently known user information. User interaction, refinement of the matrix factorization, and optimization are iterated. An experimental evaluation analyzes the performance of COA with special consideration of the number of user interactions required to find near optimal solutions. The algorithm is tested on artificial instances, as well as instances derived from real-world taxi data from Manhattan. Results show that the approach can effectively solve instances with hundreds of potential service point locations and thousands of users, while keeping the user interactions reasonably low. A bound on the number of user interactions required to obtain full knowledge of user preferences is derived, and results show that with 50% of performed user interactions the solutions generated by COA feature optimality gaps of only 1.45% on average.https://www.mdpi.com/1999-4893/14/8/232heuristic optimizationlocation planningcooperative optimizationpreference learning |
| spellingShingle | Thomas Jatschka Günther R. Raidl Tobias Rodemann A General Cooperative Optimization Approach for Distributing Service Points in Mobility Applications Algorithms heuristic optimization location planning cooperative optimization preference learning |
| title | A General Cooperative Optimization Approach for Distributing Service Points in Mobility Applications |
| title_full | A General Cooperative Optimization Approach for Distributing Service Points in Mobility Applications |
| title_fullStr | A General Cooperative Optimization Approach for Distributing Service Points in Mobility Applications |
| title_full_unstemmed | A General Cooperative Optimization Approach for Distributing Service Points in Mobility Applications |
| title_short | A General Cooperative Optimization Approach for Distributing Service Points in Mobility Applications |
| title_sort | general cooperative optimization approach for distributing service points in mobility applications |
| topic | heuristic optimization location planning cooperative optimization preference learning |
| url | https://www.mdpi.com/1999-4893/14/8/232 |
| work_keys_str_mv | AT thomasjatschka ageneralcooperativeoptimizationapproachfordistributingservicepointsinmobilityapplications AT guntherrraidl ageneralcooperativeoptimizationapproachfordistributingservicepointsinmobilityapplications AT tobiasrodemann ageneralcooperativeoptimizationapproachfordistributingservicepointsinmobilityapplications AT thomasjatschka generalcooperativeoptimizationapproachfordistributingservicepointsinmobilityapplications AT guntherrraidl generalcooperativeoptimizationapproachfordistributingservicepointsinmobilityapplications AT tobiasrodemann generalcooperativeoptimizationapproachfordistributingservicepointsinmobilityapplications |