Publication Type

Conference Proceeding Article

Version

acceptedVersion

Publication Date

5-2015

Abstract

Profitable tour problem (PTP) belongs to the class of vehicle routing problem (VRP) with profits seeking to maximize the difference between the total collected profit and the total cost incurred. Traditionally, PTP involves single vehicle. In this paper, we consider PTP with multiple vehicles. Unlike the classical VRP that seeks to serve all customers, PTP involves the strategic-level customer selection so as to maximize the total collected profit and the operational-level route optimization to minimize the total cost incurred. Therefore, PTP is essentially the knapsack problem at the strategic level with VRP at the operational level. That means the evolutionary bi-level programming would be a suitable choice of methodology for solving the NP-hard PTP. Employing some evolutionary method to solve the bi-level program naively would undoubtedly be prohibitively expensive. We thus present in this paper the notion of knowledge adoption to approximate the initial solution to the lower-level optimization problem for a given trial solution of the upper-level decision variables. One may consider the knowledge adoption as a special case of knowledge transfer in which the transfer takes place within the same problem domain. Refining the approximate initial solution with local search forces it to quickly converge to some locally optimal solution. The better the estimation of the initial solution, the closer the local optimum will be to the global one. PTP finds its important application in the fields of transportation and logistics. In addressing last-mile problem using auction at the urban consolidation center (UCC), PTP plays a significant role in the winner determination problem (WDP) that follows. Empirical study demonstrates the efficacy of the proposed approach in solving the PTP-based WDP, yielding significantly higher profit, utilization, and service level compared to when the UCC adopts the conventional WDP based on multiple knapsack problem (i.e. the MKP-based WDP).

Keywords

Bi-level programming, Customer selections, Evolutionary method, Multiple knapsack problem, Optimization problems, Urban consolidation, Vehicle routing problem, Winner determination problem

Discipline

Computer Sciences | Operations Research, Systems Engineering and Industrial Engineering | Transportation

Research Areas

Intelligent Systems and Optimization

Publication

IEEE International Congress on Evolutionary Computation CEC 2015: Proceedings, 25-28 May 2015, Sendai, Japan

First Page

2713

Last Page

2720

ISBN

9781479974924

Identifier

10.1109/CEC.2015.7257225

Publisher

IEEE

City or Country

Piscataway, NJ

Embargo Period

1-3-2017

Copyright Owner and License

Authors

Additional URL

https://doi.org/10.1109/CEC.2015.7257225

Download

Share

COinS