A GRASP-based Solution Construction Approach for the Multi-Vehicle Profitable Pickup and Delivery Problem

With the advancement of e-commerce and Internet shopping, the high competition between carriers has made many companies rethink their service mechanisms to customers, in order to ensure that they stay competitive in the market. Therefore, companies with limited resources focus on serving only customers who provide high profits at the lowest possible cost. The Multi-Vehicle Profitable Pickup and Delivery Problem (MVPPDP) is a vehicle routing problem and one variant of the Selective Pickup and Delivery Problem (SPDP) that is considered to plan the services for these types of companies. The MVPPDP aims to serve only the profitable customers, where the products are transformed from a selection of pickup customers to the corresponding delivery customers, within a given travel time limit. In this paper, we utilize the construction phase of the well-known Greedy Randomized Adaptive Search Procedure (GRASP) to build initial solutions for the MVPPDP. The performance of the proposed method is compared with two greedy construction heuristics that were previously used in the literature to build the initial solutions of the MVPPDP. The results proved the effectiveness of the proposed method, where eight new initial solutions are obtained for the problem. Our approach is especially beneficial for building a population of solutions that combine both diversity and quality, which can help to obtain good solutions in the improvement phase of the problem.

@article{Alhujaylan2019,
  title     = {A GRASP-based Solution Construction Approach for the Multi-Vehicle Profitable Pickup and Delivery Problem},
  journal   = {International Journal of Advanced Computer Science and Applications},
  volume    = {10},
  number    = {4},
  year      = {2019},
  publisher = {The Science and Information Organization},
  author    = {Abeer I Alhujaylan and Manar I. Hosny},
  doi       = {10.14569/IJACSA.2019.0100412},
  url       = {https://doi.org/10.14569/IJACSA.2019.0100412}
}