Featured Story January - February 2013
The Consistent Vehicle Routing Problem with Profits

by Dr Foteini Stavropoulou, Research Fellow

Customer services offered by numerous companies require that employees, such as workers, drivers, sales representatives etc., visit customers on a regular basis. Consistent patterns with respect to the time of visit and the visiting employee can enhance brand loyalty by allowing the company's employees to develop relations with the customers. Brand loyalty is desired in the current dynamically changing and unstable economic environment, as it is a key factor to strengthen the company's position in the market and secure or even expand the corresponding market share. To this end, in recent years more and more companies tend to focus and invest on customer relationship management, and thereafter, they are interested in providing consistent customer-oriented services.

Customer services offered by numerous companies require that employees, such as workers, drivers, sales representatives etc., visit customers on a regular basis. Consistent patterns with respect to the time of visit and the visiting employee can enhance brand loyalty by allowing the company's employees to develop relations with the customers. Brand loyalty is desired in the current dynamically changing and unstable economic environment, as it is a key factor to strengthen the company's position in the market and secure or even expand the corresponding market share. To this end, in recent years more and more companies tend to focus and invest on customer relationship management, and thereafter, they are interested in providing consistent customer-oriented services.

To this end, a new problem is introduced, the Consistent Vehicle Routing Problem with Profits (ConVRP with Profits). This new transportation logistics problem aims to maximize a company's net acquired profits and to expand its customer base, while providing consistent customer service utilizing all available enterprise resources. It is inspired by the practical application in which a company attempts to service additional customers to the regular ones and needs to decide which non-regular customers should be serviced. Given a set of mandatory frequent customers and potential non-frequent ones with known demands, profits and service requirements over a planning horizon, the aim is to design routes that maximize the difference between the total acquired profit and the total traveling cost, using a homogeneous fleet of capacitated depot-returning vehicles of fixed size. All frequent customers must be visited only once by the same vehicle whenever they require service such that the maximum difference between the earliest and latest vehicle arrival times over the planning horizon does not exceed a specific time limit. On the other hand, the potential non-frequent customers can be visited at most once by any vehicle. The goal is to determine the corresponding vehicle routes for the planning horizon without violating the predefined vehicle capacity, route duration and consistency constraints. An example of a possible ConVRP with Profits solution is the following:


Copyright 2013 Website Design by Pantelis Lappas. All rights reserved.
ConVRP with Profits is an NP-hard combinatorial optimization problem, as a generalization of the Profitable Tour Problem (PTP) [2]. Computationally complex combinatorial optimization problems appear in a plethora of real-world applications of great economic, industrial and scientific importance and usually as large-scale problems. Thus, the development of efficient and effective algorithms is a challenging task of obvious importance.

Computationally intelligent approaches that explore the solutions space with strategic guidance is a very promising research area. For this purpose, hybrid algorithms and intelligent frameworks that combine several metaheuristic algorithms are developed. The development of hybrid optimization algorithms is a new trend of research and is based on collaborative combinations. In collaboration scheme algorithms exchange information among independent procedures executed in a sequential, intertwined or parallel fashion. Thus, an intelligent framework may incorporate metaheuristic algorithms with complementary characteristics in order to effectively search the solutions space in reasonable computational time.

References

[1] Groer C, Golden BL and Wasil E, The consistent vehicle routing problem, Manufacturing & Service Operations Management, 11(4),630-643 (2009).

[2] Archetti C, Feillet D, Hertz A and Speranza MG, The capacitated team orienteering and profitable tour problems, Journal of the Operational Research Society 60, 831-842 (2009).



M A N A G E M E N T    S C I E N C E    L A B O R A T O R Y   

ACADEMICS
........................

RESEARCH
........................

PEOPLE
........................

MS SUPPORT
........................

ARCHIVE
......................

DOWNLOAD
......................

ABOUT
..................

CONTACT
..................