1. the complete title of one (or more) paper(s) published in the open literature describing the work that the author claims describes a human-competitive result

Heuristic Sequence Selection for Inventory Routing Problem

2. the name, complete physical mailing address, e-mail address, and phone number of EACH author of EACH paper(s)

Ahmed Kheiri, Lancaster University Management School, Department of Management Science, Lancaster, LA1 4YX, United Kingdom, a.kheiri@lancaster.ac.uk, T: +44 (0)1524 593117

3. the name of the corresponding author (i.e., the author to whom notices will be sent concerning the competition)

Ahmed Kheiri

4. the abstract of the paper(s)

In this paper, an improved sequence-based selection hyper-heuristic method for the AirLiquide inventory routing problem, the subject of the ROADEF/EURO 2016 challenge, is described. The organisers of the challenge have proposed a real-world problem of inventory routing as a difficult combinatorial optimisation problem. An exact method often fails to find a feasible solution to such problems. On the other hand, heuristics may be able to find a good quality solution that is significantly better than those produced by an expert human planner. There is a growing interest towards self configuring automated general-purpose reusable heuristic approaches for combinatorial optimisation. Hyper-heuristics have emerged as such methodologies. This paper investigates a new breed of hyper-heuristics based on the principles of sequence analysis to solve the inventory routing problem. The primary point of this work is that it shows the usefulness of the improved sequence-based selection hyper-heuristic, and in particular demonstrates the advantages of using a data science technique of hidden Markov model for the heuristic selection.

5. a list containing one or more of the eight letters (A, B, C, D, E, F, G, or H) that correspond to the criteria (see above) that the author claims that the work satisfies

(D) The result is publishable in its own right as a new scientific result independent of the fact that the result was mechanically created
(F) The result is equal to or better than a result that was considered an achievement in its field at the time it was first discovered
(G) The result solves a problem of indisputable difficulty in its field
(H) The result holds its own or wins a regulated competition involving human contestants (in the form of either live human players or human-written computer programs)

6. a statement stating why the result satisfies the criteria that the contestant claims (see examples of statements of human-competitiveness as a guide to aid in constructing this part of the submission)

(D) The result is publishable in its own right as a new scientific result independent of the fact that the result was mechanically created

Our approach (which utilises novel hyper-heuristic technique) has been successfully applied to a real-world Inventory Routing Problem (IRP) from AirLiquide (https://www.airliquide.com/), a world frontrunner company in gases, technologies and services for Industry and Health in almost 80 countries. The result is publishable in its own right for two reasons: Firstly, AirLiquide and other transportation industries are specifically interested in obtaining accurate solutions that enable them to better manage their resources, therefore the resulting solution is important and of practical use, regardless of how the result was generated. Secondly, the method proposed in this work is new, based on the idea of dynamically exploring the neighbourhood by combining sequences of basic heuristics to modify certain region of the solution space. This approach was new compared with the classical local search, which is natively static in the choice of heuristics. Each sequence of heuristics is built by a hidden Markov model, and each arc connecting two heuristics is chosen based on the previous iterations, because the value associated to the link is reinforced by previous results. Such ready-to-use high level hyper-heuristic methods can be applied to a wide range of real-world problems.

(F) The result is equal to or better than a result that was considered an achievement in its field at the time it was first discovered

The paper provides the best results by far, which underlines that for solving real-life instances, the approaches based on exact algorithms [1-3] are still insufficient [4]. One may add that our approach promotes the field of Genetic and Evolutionary Computation as the best in tackling large scale problems (in terms of the complexity of the constraints and the size of the instances solved).

[1] Absi N, Cattaruzza D, Feillet D, Ogier M, Semet F (2020) A heuristic branch-cut-and-price algorithm for the ROADEF/EURO Challenge on inventory routing. Transportation Science, 54(2):313–329.
[2] He Y, Artigues C, Briand C, Jozefowiez N, Ngueveu SU (2020) A matheuristic with fixed-sequence reoptimization for a real-life inventory routing problem. Transportation Science, 54(2):355–374.
[3] Su Z, Lü Z, Wang Z, Benlic U (2020) A matheuristic algorithm for the inventory routing problem. Transportation Science, 54(2):330–354.
[4] Andre J, Bourreau E, Calvo RW (2020) Introduction to the Special Section: ROADEF/EURO Challenge 2016—Inventory Routing Problem. Transportation Science, 54(2):299-564.

(G) The result solves a problem of indisputable difficulty in its field

The characteristics of the problem tackled in this work are new with respect to the literature on the inventory routing problem (IRP) as reported in the 2020 paper cited below. The main features are the following: a non-linear objective function (logistics ratio), multi-day shifts, multi-sourcing, and the scheduling of drivers and routing of trailers at the same time. This latter characteristic imposes the need to define the starting times of the routes, which can be at any time of the day, and the quantities to refill. Thus, the problem has several components which must be jointly optimised. The last, but not least, characteristic is the size of the instances, because the large instances have a huge number of customers (up to 300 customers) over long time horizons (more than 30 days).
The hardness of this problem is also acknowledged by the reviewers of the Transportation Science - the foremost journal in the field of transportation, who accepted the paper.

Jean Andre, Eric Bourreau, Roberto Wolfler Calvo (2020) Introduction to the Special Section: ROADEF/EURO Challenge 2016—Inventory Routing Problem. Transportation Science, 54(2):299-564.

(H) The result holds its own or wins a regulated competition involving human contestants (in the form of either live human players or human-written computer programs)

The problem was a subject of the ROADEF/EURO 2016 challenge, and the results demonstrate the effectiveness of the hyper-heuristic method, being the winner of the challenge against 41 teams across 16 different countries, producing the best solutions across all of the released problem instances - a first in the history of the challenge. The ROADEF/EURO challenge is largest of its kind globally in our field.

7. a full citation of the paper (that is, author names; publication date; name of journal, conference, technical report, thesis, book, or book chapter; name of editors, if applicable, of the journal or edited book; publisher name; publisher city; page numbers, if applicable)

Ahmed Kheiri (2020) Heuristic sequence selection for inventory routing problem. Transportation Science, 54(2):302-312. INFORMS https://doi.org/10.1287/trsc.2019.0934

8. a statement either that "any prize money, if any, is to be divided equally among the co-authors" OR a specific percentage breakdown as to how the prize money, if any, is to be divided among the co-authors

This is a single authored paper.

9. a statement stating why the authors expect that their entry would be the "best"

The reasons for being the "best" are:
+ We dealt with complex optimisation problem which integrates related problems that are traditionally solved separately, thus leading to sub-optimal solutions. There is a wide range of decisions that have to be optimised, such as assignment of drivers to trailers, scheduling of drivers, routing, quantities to refill, all subject to a large set of constraints
+ The objective function (currently minimising the time cost, minimising the distance cost, minimising the layover cost and maximising the total quantity delivered over the whole horizon) can be tuned or switched for another one easily. In fact, our model allows the user to choose weights for different objectives to reflect operator's business objectives
+ We developed a high-level strategy that aims to raise the level of generality and able to solve other real-world optimisation problems given only minimal domain knowledge. Further, the set of low level heuristics can be adjusted easily and extended with other low level heuristics as required
+ Our approach obtained significantly better results than other competing methods, providing a new scientific method and a state-of-the-art result. After few seconds (less than 3 minutes), our algorithm creates solutions of a far better quality than other methods and than those of humans taking months of planning. This speed allows an efficient re-optimisation of an instance if it is changed, and allows for rapid tests of different objective functions
+ The proposed method showcased very well the merits of Genetic and Evolutionary Computation methods compared to other optimisation approaches
+ The method has potential to achieve considerable economic impact to AirLiquide and other transportation industries. An agreement has already been signed with AirLiquide to employ the developed method (as described in the paper) for optimising their resources
+ Finally, the work has been published in a leading journal and already read by/discussed with major transportation industries (AirLiquide, Linde, Optrak, CACI and TESCO). This raises the profile of practical Evolutionary Computing

10. An indication of the general type of genetic or evolutionary computation used, such as GA (genetic algorithms), GP (genetic programming), ES (evolution strategies), EP (evolutionary programming), LCS (learning classifier systems), GE (grammatical evolution), GEP (gene expression programming), DE (differential evolution), etc

ECOM (Evolutionary Combinatorial Optimisation and Metaheuristics)

11. The date of publication of each paper.  If the date of publication is not on or before the deadline for submission, but instead, the paper has been unconditionally accepted for publication and is "in press" by the deadline for this competition, the entry must include a copy of the documentation establishing that the paper meets the "in press" requirement

Published Online: 9 Mar 2020