Metaheuristics for Logistics
Metaheuristics for Logistics
Logistic problems are all around us. We only need to observe a little and to have some imagination to find them. In this chapter we propose three problems that perfectly illustrate the potential touch of madness of an operations researcher. These examples enable us to approach the issues that may crop up in the industrial world gradually, which will be described more formally in the following chapters. They are drawn from exam papers assigned to undergraduate students that have taken classes in a subject called "optimization problems and procedures". They are kept in their original form on purpose. The questions asked will be answered over the course of this book. A detailed answer key for the exercises, including comments, is supplied in the last chapter of this book. Beginners in combinatorial optimization can play the following little game: could you recognize the correlation between each practical problem and its theoretical equivalent?
1.1. The "swing states" problem
In the United States of America, during the presidential elections, there are certain states called "swing states", which are liable to swing from the Democratic Party towards the Republican or vice versa. It is these states that both parties pay most attention to, especially when the results day is drawing near. Table 1.1 shows the list of these states and the figures of their Electoral College.
The advisers of one of two candidates (you are free to choose either side) ask you to help them make the most of their last week of campaigning. You are also provided with, in Table 1.1 , an estimate of the sum that needs to be invested in every state in order to have a chance to command a majority. There is a $500,000 global budget left to invest. The question is simple: which states should you choose in order to win the greatest number of electors?
Table 1.1. List of "swing states" and estimate of the investment necessary to obtain a majority
Swing states Electoral College Invested sum (in K$) North Carolina 15 80 Colorado 9 50 Florida 27 200 Indiana 11 70 Missouri 11 80 New Hampshire 4 30 New Mexico 5 50 Nevada 5 40 Ohio 20 150 Pennsylvania 21 110 Virginia 13 80 Wisconsin 10 60
1) What kind of combinatorial optimization problem is the "swing state" problem in relation with?
2) Determine a criterion according to which the states can be ranked from most interesting to least interesting. Deduce a construction heuristic from this and give its principle. What solution do you find?
3) Remove the most expensive state from the last solution. Can you then complete your solution by choosing some other states, thus improving it?
4) Deduce a neighborhood system for this problem.
5) Propose the most appropriate upper and lower bounds of the optimal solution. 1.2. Adel and his camels
Your favorite Operations Research professor (we will call him Mr L.), having barely arrived in Douz 1 , meets Adel, a professional camel driver. Mr L., after introducing Adel to Operations Research, works out a deal for a free excursion to the Sahara. In exchange,