On investigation of interdependence between subpr

Authors: Yi Mei Xiaodong Li Xin Yao

Publish Date: 2014/10/17

Volume: 20, Issue: 1, Pages: 157-172

PDF Link

Abstract

In this paper the interdependence between subproblems in a complex overall problem is investigated using a benchmark problem called Travelling Thief Problem TTP which is a combination of Travelling Salesman Problem TSP and Knapsack Problem KP First the analysis on the mathematical formulation shows that it is impossible to decompose the problem into independent subproblems due to the nonlinear relationship in the objective function Therefore the algorithm for TTP is not straightforward although each subproblem alone has been investigated intensively Then two metaheuristics are proposed for TTP One is the Cooperative Coevolution CC that solves the subproblems separately and transfers the information between them in each generation The other is the Memetic Algorithm MA that solves TTP as a whole The comparative results showed that MA consistently obtained much better results than both the standard and dynamic versions of CC within comparable computational budget This indicates the importance of considering the interdependence between subproblems in an overall problem like TTPRealworld problems often involve a large number of decision variables and constraints making it impossible to find the global optimal solution within the given time budget When tackling largescale optimization problems the divideandconquer approach is commonly adopted to decompose the overall problem into smaller subproblems Boyd et al 2007 Omidvar et al 2014 Mei et al 2014a For many realworld problems the subproblems are naturally defined For example in supply chain management Thomas and Griffin 1996 Stadtler 2005 Melo et al 2009 each stage or operation such as procurement production and distribution can correspond to a subproblem However it is often inevitable that such subproblems are still interdependent on each other As mentioned in Michalewicz 2012 one of the main complexity of realworld problems is the interdependence between subproblems which makes many conventional approaches ineffective As a result even if each subproblem has been intensively investigated it is still an open question how to integrate the highquality partial solutions for the subproblems to obtain a global optimum or at least a highquality solution for the overall problem Therefore it is important to investigate how to tackle the interdependence between subproblemsTo facilitate such investigation Bonyadi et al 2013 recently defined a benchmark problem called Travelling Thief Problem TTP TTP is a combination of two wellknown combinatorial optimization problems ie Travelling Salesman Problem TSP and Knapsack Problem KP Specifically a thief is to visit a set of cities and pick some items from the cities to put in a rented knapsack Each item has a value and a weight The knapsack has a limited capacity that cannot be exceeded by the total weight of the picked items In the end the thief has to pay the rent for the knapsack which depends on the travel time TTP aims to find a tour for the thief to visit all the cities exactly once pick some items along the way and finally return to the starting city so that the benefit of the visit which is the total value of the picked items minus the rent of the knapsack is maximized Since TSP and KP have been intensively investigated TTP facilitates to concentrate on the interdependence between subproblemsAn example of potential relevant realworld applications of TTP is the capacitated arc routing problem Dror 2000 with service profit Although there have been extensive studies for solving various forms of the capacitated arc routing problem depending on different practical scenarios eg the classic model Mei et al 2009a b Tang et al 2009 Fu et al 2010 the multiobjective model Mei et al 2011a the stochastic model Mei et al 2010 the periodic model Mei et al 2011b and the largescale model Mei et al 2013 2014a b two important practical issues have been overlooked so far One is the service profit which is the profit that can be gained by serving the customers Each customer may have a different profit/demand ratio Thus given the limited capacity of the vehicle one may need to serve only a subset of the customers with higher profit/demand ratios to maximize the final benefit The other factor is the dependency of the travel cost of the vehicle on its load Obviously a heavier load of the vehicle leads to a higher consumption of petrol and thus a higher travel cost In this case it would be more desirable to serve the customers with a higher demand first to save the travel cost of the subsequent route With the above factors taken into account the resultant arc routing problem can be modelled as a TTPIn this paper the interdependence of TSP and KP in TTP is investigated both theoretically and empirically First the mathematical formulation of TTP is developed and analysed to show how the two subproblems interact with each other Then a Cooperative Coevolution algorithm CC including a standard and a dynamic version and a Memetic Algorithm MA are developed CC solves TSP and KP separately and transfers the information between them in each generation MA solves TTP as a whole Standard crossover and mutation operators are employed The proposed algorithms were compared on the benchmark instances proposed in Bonyadi et al 2013 and the results showed that MA managed to obtain much better solutions than CC for all the test instances In other words with the same crossover and mutation operators for each subproblem a more proper way of integrating the optimization process of the subproblems can result in a significantly better solution This demonstrates that considering the interdependence between subproblems is important for obtaining highquality solution for the overall problem Moreover the theoretical analysis establishes the fundamental understanding of the problemThe rest of the paper is organized as follows TTP is formulated and analysed in Sect 2 After that CC and MA are depicted in Sect 3 Then the experimental studies are carried out in Sect 4 Finally the conclusion and future work are described in Sect 5

Keywords: