HybridMOOP: Client-centered multi-objective optimization

Project Leader: Sophie N. Parragh
Co-Authors: Karl F. Doerner, Fabien Tricoire
Project Collaborators: Thibaut Barthelemy, Michael Bögl, Fabien Tricoire
Funding Body: Austrian Science Fund (FWF)
Project Number: P23589-N13
Duration: Sep 2011 – Aug 2015

Abstract Client-centered logistics problems appear in many highly relevant areas of our daily life. They range from the design of public transportation networks to field workforce scheduling in private service companies. Many of these problems have in common that, besides a cost-oriented objective, there also exists a user-centered objective. These two goals are usually contradicting: lower costs lead to lower quality of service and vice versa. The respective decision makers are confronted with the task of assigning weights to the different objectives, representing their preferences. However, a compromise solution, computed based on these weights, lacks important additional information. This information concerns the tradeoff between costs and quality of service: would higher quality of service be possible at only little additional cost? One possibility to circumvent this problem consists in the application of multi-objective optimization methods. These methods generate a set of “equally good” compromise solutions, allowing the decision maker to choose the most appropriate one. In the single-objective field, combinations of exact and heuristic search methods, so-called hybrid methods, have been particularly successful. In multi-objective combinatorial optimization, hybrid methods of this type have been barely investigated. This fact constitutes the fundamental motivation for this research project and at the same time defines its aim: the development of hybrid search methodsfor logistics problems with multiple objectives, in a first step, limited to client-centered logistics problems, such as public service location, school bus routing or service technician routing and scheduling. The strengths as well as the weaknesses of the developed methods will be thoroughly analyzed, and general guidelines, telling under which circumstances and for which problem class the different methods are best suitable, will be derived.

Activities

Workshop organization: “Recent Advances in Multi-Objective Optimization” moo.univie.ac.at

  • Workshop 2014: 1st International Workshop, September 12, 2014, Vienna, Austria; organised by Ivana Ljubic and Sophie Parragh; 2 keynote talks, 11 invited talks.
  • Workshop 2015: 2nd Edition, June 19, 2015, Nantes, France; organized by Xavier Gandibleux, Anthony Przybylski, Audrey Cerqueus

Mailing List for “Recent Advances in Multi-Objective Optimization” subscribe here

Featured Cluster at EJOR: “Recent Advances in Exact Methods for Multi-Objective Optimisation”, edited by Matthias Ehrgott, Ivana Ljubic, and Sophie Parragh; NEW Submission deadline:  Sep 1, 2015, Link to CfP

Session organization “Multi-Objective Optimization in Transport and Logistics I and II”  at OR 2015,  Vienna, Sep 1-4, 2015.

Journal publications

  1. Parragh, S.N., Tricoire, F., Gutjahr, W.J. (2021) A branch-and-Benders-cut algorithm for a bi-objective stochastic facility location problem. OR Spectrum, https://doi.org/10.1007/s00291-020-00616-7 Preprint: https://arxiv.org/abs/2004.11248
  2. Braekers, K., Hartl, R.F., Parragh, S.N., Tricoire, F. (2016). A bi-objective home care scheduling problem: Analyzing the trade-off between costs and client inconvenience.  European Journal of Operational Research 248(2), 428€“443. http://dx.doi.org/10.1016/j.ejor.2015.07.028 (Open Access)
  3. Boegl, M., Doerner, K.F., Parragh, S.N. (2015). The school bus routing and scheduling problem with transfers. Networks, 65(2), 180-203. http://dx.doi.org/10.1002/net.21589 (Open Access)

Technical reports submitted for publication

  1. Barthelemy, T., Parragh, S.N. Tricoire, F., Hartl. R.F. (2015) Beam Search for integer multi-objective optimization, submitted. http://www.optimization-online.org/DB_HTML/2015/04/4879.html
  2. Parragh, S.N. Tricoire, F. (2014), Branch-and-bound for bi-objective integer programming, submitted. http://www.optimization-online.org/DB_HTML/2014/07/4444.html

Presentations at scientific conferences

  1. Bögl, M. (2012) The school bus routing and scheduling problem with mixed loads and transfers. VeRoLog Conference 2012, Bologna, 17.06-21.06.2012. Abstract (pdf)
  2. Bögl M. (2013) A destroy and repair search heuristic for the school bus routing and scheduling problem with transfers. VeRoLog Conference 2013, Southampton, 07.07-10.07.2013. Abstract (pdf)
  3. Tricoire, F. (2013) Bound sets for the biobjective team orienteering problem with time windows.  VeRoLog Conference 2013, Southampton, 07.07-10.07.2013. Abstract (pdf)
  4. Barthelemy, T. (2014) A multi-objective Recovering Beam Search and its application to the TSP with Profits. ISCO 2014 Conference, Lisbon, 04.03-08.03.2014.
    Abstract A Beam Search procedure is a breadth-first Branch & Bound where, at each level of the search tree, up to W nodes are kept only. That results in a meta-heuristic whose solving time is polynomial in the number of variables and W. Several authors chose Beam Search to solve single-objective problems, mostly scheduling-related ones, while only 2 articles address multi-objective optimization. In particular, there is no paradigm stating what a good node selection could be. In our Beam Search, we study five components (node evaluation, node selection, branching and two branching improvements). To design each one in a likely good way, a few theory and discussion are given. By means of experiments on the bi-objective TSP with Profits (BOTSPP), we show that they contribute to good results. The BOTSPP consists in finding cycles in a graph such that the sum of weights of the traversed edges is minimized while the sum of weights of the selected vertices is maximized.
  5. Tricoire, F. (2014) Branch and bound for the biobjective team orienteering problem with time windows. VeRoLog Conference 2014, Oslo, 22.06.-26.06.2014.
    Abstract In the team orienteering problem with time windows (TOPTW), a set of control points can be visited, each of them providing a certain profit. A limited fleet of vehicles, each subject to a total time limit, is used to maximize the profit of visited control points. In this work we tackle the biobjective TOPTW (BITOPTW). It is a variant of the TOPTW in which the constraint on total duration is relaxed and reintroduced as an objective. We use the Pareto approach, in which every nondominated solution is considered efficient and part of the optimal set. We develop an exact method, meaning that every solution in the efficient set is generated. In order to produce the whole efficient set we design a generalization of the branch-and-bound algorithm to biobjective optimization with integer variables. Lower- and upper-bound sets are considered and fathoming rules are extended to consider sets instead of single values. The lower bound set is generated using column generation, since it typically provides a tighter bound than compact formulations for routing problems. Specific branching rules are designed for (i) the problem at hand and (ii) any biobjective problem. Experimental results demonstrate the viability of our approach.
  6. Barthelemy, T. (2014) Beam Search for integer multi-objective optimization. OR 2014, International Conference on Operations Research, Aachen, 02.09.-06.09.2014.
    Abstract Beam search is a tree search procedure where, at each level of the tree, at most W nodes are kept. That results in a meta-heuristic whose solving time is polynomial in both W and the number of variables as long as node selection is decided in polynomial time.Although popular for solving single-objective problems (mostly scheduling-related ones), beam search has been studied for multi-objective optimization by two teams so far. The approaches have three fundamental components in common: branching scheme, variable selection and node pruning. Authors do not analyze influence of the branching scheme on solution quality. Regarding the decision rule for selecting the variable to branch on at each tree-node, they notice a strong influence on the quality. Pruning the nodes in polynomial time is made in various ways. Our work studies those three components and explains their influence. Relying on theoretical grounds, we advice their design and show that specificities due to the multiplicity of objectives must be regarded. In particular, we clearly divide the node pruning process into two phases, respectively node quality evaluation and node selection, whose desirable properties are identified and refined individually through empirical processes.At last, those versatile considerations are applied to the bi-objective Knapsack Problem and the bi-objective Traveling Salesman Problem with Profits. Thus, the benefits from our guidelines are shown component by component. The so-obtained Knapsack solver outperforms the previous dedicated beam search of literature. The TSP results will allow authors for future comparisons.
  7. Barthelemy, T. (2015) On properties and the complexity of multi-criteria sorting algorithms, OR 2015, International Conference on Operations Research, Vienna, 01.09.-04.09.2015.
    Abstract Multi-criteria sort consists in ranking points lying in a d-dimensional space with d > 1.It plays an important role in metaheuristics for multi-objective optimization. Whereas the evolutionary algorithm SPEA sorts solutions, represented by points in objective space, with respect to a dominance count, NSGA sorts with respect to dominance relations. Other metaheuristics assess the point coordinates through a scalar indicator and they rank the points using standard single-criterion sorting.From a generalized point of view, one can categorize ranking approaches with respect to their properties, including some inherited from voting theory. We study lower bounds on the complexity of sorting algorithms according to their category. At last, we give ideas for implementing a non-dominated sort whose average complexity in practice is expected to be close to O[n log n] even for high dimensions while the best worst case complexity known so far is O[n (log n)^(d-1)].
  8. Tricoire, F. (2015) Bi-objective stochastic facility location. OR 2015, International Conference on Operations Research, Vienna, 01.09.-04.09.2015.
    Abstract We investigate facility location for service facilities in the broad sense. This includes for instance public service such as post offices, or other kinds of service-based businesses that require to locate facilities. In that context, the ability to provide service to a large part of the population is highly relevant, and typically comes at the cost of opening more facilities. Demand emanates from regions, each region representing a certain population, for instance a village in a rural context. Additionally, it is not always possible to assume that demand data are deterministic, as the decision maker has limited control over where people actually decide to go. For the same reason, demand from a given region can be split and service can be provided to this region concurrently by several facilities. We consider a bi-objective stochastic optimization problem where the two objectives are the minimization of uncovered demand and the minimization of cost. The demand is stochastic. There are several methods to solve bi-objective optimization problems. We compare the well-known epsilon-constraint framework and a more recent bi-objective branch-and-bound algorithm which we previously introduced. Both methods rely on iteratively solving modified linear programs (LPs), so we consider that the stochastic LP is solved by a black box algorithm. Stochasticity is modeled using samples. We then incorporate these samples in the model, transforming the stochastic LP into a deterministic one. However this results in a much bigger LP. We also investigate using the L-shaped method to solve the stochastic LP without creating as many variables and constraints. All four combinations of bi-objective framework and stochasticity treatment are tested and compared using existing data.
  9. Parragh, S.N. (2015) Evaluating the trade-off between cost and service-oriented objectives in routing and scheduling problems. OR 2015, International Conference on Operations Research, Vienna, 01.09.-04.09.2015.
    Abstract In many routing and scheduling problems besides cost also service-oriented objectives are of concern. In order to shed some light on their trade-off relationship, we introduce separate service-oriented objectives into the generalized consistent vehicle routing problem (GenConVRP) and into the home care routing and scheduling problem (HCRSP). In the resulting multi-objective GenConVRP we concurrently optimize routing costs and two service-oriented objectives. The first accounts for the maximum number of different drivers visiting a given customer (known as driver consistency) and the second for the maximum arrival time difference during the planning horizon (known as arrival time consistency). Frequent customers have demands on several days in the planning horizon while non-frequent customers require a service only once. Each customer is associated with an AM or a PM time window and waiting along the route is not allowed. In the bi-objective HCRSP we minimize routing and overtime costs and we maximize the service level with respect to preferences for visit times and nurses. Overtime costs in combination with interval preferences on preferred visit times results in a scheduling problem for each route that is a bi-objective problem in itself, which is a distinctive characteristic of the bi-objective HCRSP. Furthermore, each client is associated with a time window and waiting within the time window to improve service levels is not allowed. For both problems we solve small instances to optimality using the epsilon-constraint scheme. To solve larger (real world) instances we devise algorithms combining large neighborhood search and multi-directional local search. We can show that a considerable trade-off between cost and client-oriented objectives exists. However, our results also reveal that, using the minimum cost solution as a basis, the considered service levels may be improved drastically with only small additional costs; and that in the GenConVRP, in several cases, arrival time consistency and driver consistency can be improved simultaneously.

Invited talks and seminars

  1. Bögl, M. (2013) Synchronization issues in the school bus routing and scheduling problem with transfers. SynchroTrans Workshop on invitation basis, Mainz, 26.05-29.05.2013
  2. Parragh, S.N. (2014) Solving the bi-objective team orienteering problem by branch and price. ANOG Workshop €œRouting and Networks€, Vienna, Austria, 15.01.2014.
  3. Doerner, K.F. (2014) The school bus routing and scheduling problem with transfers.
    ANOG Workshop €œRouting and Networks€, Vienna, Austria, 15.01.2014.
  4. Parragh, S.N. (2014) Bi-objective branch-and-bound and its application to the team orienteering problem with time windows. Research seminar, Institute for Statistics and Operations Research, University of Graz, Graz, Austria, 20.05.2014.
  5. Doerner, K.F. (2014) Matheuristics Design Concepts for Rich Problems, Semiplenary at the GOR Meeting 2014 (OR 2014) in Aachen, September, 4-6, 2014. Aachen, Germany.
  6. Tricoire, F. (2014) Linear programming for bi-objective stochastic logistics. International Workshop on Recent Advances in Multi-Objective Optimization 2014, Vienna, Austria, 18.09.2014
  7. Doerner, K.F. (2014) Matheuristics Design Concepts for Rich Problems, Research Seminar at the SCM Institute of the WU Wien, December, 15, 2014. Wien, Austria.
  8. Doerner, K.F. (2015) Heuristic Solution Approaches for the School Bus Routing and Scheduling Problem with Transfers, NOW 2015 Workshop on invitation basis, May, 18-20, 2015. La Rochelle, France.
  9. Doerner, K.F. (2015) Passenger Transportation in Rural Areas, VHB Pfingsttagung,
    May, 27-29, 2015. Vienna, Austria.