A multi-objective open set orienteering problem
- PDF / 1,532,595 Bytes
- 17 Pages / 595.276 x 790.866 pts Page_size
- 68 Downloads / 167 Views
(0123456789().,-volV)(0123456789(). ,- volV)
ORIGINAL ARTICLE
A multi-objective open set orienteering problem Joydeep Dutta1 • Partha Sarathi Barma1 • Anupam Mukherjee2 • Samarjit Kar2 • Tanmay De3 Received: 27 August 2019 / Accepted: 17 February 2020 Ó Springer-Verlag London Ltd., part of Springer Nature 2020
Abstract We have constructed a multi-objective set orienteering problem to model real-world problems more fittingly than the existing models. It attaches (i) a predefined profit associated with each cluster of customers, and (ii) a preset maximum service time associated with each customer of all the clusters. When a customer from cluster visits, it allows the earning of a profit score. Our purpose is primarily to search for a route that (i) on the one hand allows us to service each cluster for maximizing customer satisfaction and (ii) on the other hand allows us to maximize our profits, too. The model assumes that the more time we spend on servicing, the more customer satisfaction it yields. It tries to cover as many clusters as possible within a specified time budget. In this paper, we also consider third-party logistics to allow the flexibility of ending our journey at any cluster of our choice. The proposed model is solved using the nondominated sorting genetic algorithm and the strength Pareto evolutionary algorithm. Here, we also generate the dataset to test the proposed model by using instances from the literature of the generalized traveling salesman problem. Finally, we present a comparative result analysis with the help of some statistical tools and discuss the results. Keywords Set orienteering problem Multi-objective optimization NSGAII SPEA2
1 Introduction In today’s world, successful organizations keep a constant focus on the enhancement of products and plan continuously to improve customer through suitable service. Transportation has a vital role in any industry because a proper routing plan can serve the customers more efficiently, and hence, it increases customer satisfaction, thereby increasing the goodwill of the organization. Efficient routing can reduce a lot in the cost of transportation that directly decreases product price and increases product acceptability in the market leading to an increase in consumption of the products in question. That is why researchers have given massive attention to the routing of
& Samarjit Kar [email protected] 1
Department of Computer Science and Engineering, NSHM Knowledge Campus, Durgapur, West Bengal 713212, India
2
Department of Mathematics, NIT Durgapur, Durgapur, West Bengal 713209, India
3
Department of Computer Science and Engineering, NIT Durgapur, Durgapur, West Bengal 713212, India
products or services for the last few decades. As a result, several new concepts and models of routing plans have been invented. These models directly or indirectly map real-world problems. The traveling salesman problem (TSP) published in the 1800s is the oldest and the essential concept. Here, the challenge is to find a Hamiltonian cycl
Data Loading...
