MODELS FOR PRACTICAL ROUTING PROBLEMS IN LOGISTICS
CONTENTS 1 INTRODUCTION 1 1 INTRODUCTION TO LOGISTICS 1 2 DE? NITION OF ROUTING PROBLEMS 1 3 TRAVELLING SALESMAN PROBLEM 1 4 VEHICLE ROUTING PROBLEM 1 5 CLASSES OF TRAVELLING SALESMAN AND VEHICLE ROUTING PROBLEMS 1 5 1 CLASSI? CATION OF ROUTING PROBLEMS 1 6 COMPUTATIONAL COMPLEXITY 1 7 SCOPE OF THE PRESENT BOOK 2 SURVEY OF METHODOLOGIES FOR TSP AND VRP 2 1 SOLUTION APPROACHES OF TSP AND VRP 2 1 1 TSP 2 1 2 VRP 2 2 MATHEMATICAL MODELLING 2 3 HEURISTICS 2 3 1 CONSTRUCTIVE HEURISTICS 2 3 2 TWO-PHASE HEURISTICS 2 3 3 LOCAL SEARCH IMPROVEMENT HEURISTICS 2 4 META-HEURISTICS 2 4 1 MEMORY-LESS META-HEURISTICS 2 4 2 MEMORY-BASED META-HEURISTICS 2 5 INTERACTIVE APPROACHES 2 6 HYBRID APPROACHES 2 7 APPLICATIONS OF TSP AND VRP 2 7 1 MULTIPLE INTERDEPENDENT DEPOT VRP (MIDVRP) 2 7 2 MULTIPLE COMMODITIES VRP (MCVRP) 2 7 3 VEHICLE SCHEDULING PROBLEM (VSP) 2 7 4 SCHOOL BUS ROUTING AND SCHEDULING PROBLEM (SBRSP) 2 7 5 ROUTING AND SCHEDULING WITH FULL LOADS AND TIME WINDOW (RSFLTW) 2 7 6 NEWSPAPER DISTRIBUTION VRP 2 7 7 RECYCLABLE MATERIAL COLLECTION VRP 2 7 8 EARTHQUAKE: FOOD DISTRIBUTION VRP 2 7 9 PERISHABLE FOOD DISTRIBUTION VRP 2 7 10 BANK CHEQUE COLLECTION VRP 2 7 11 VEHICLE ROUTING FOR TRANSPORTING HAZARDOUS MATERIAL 2 7 12 SHARE AUTO VRP 2 7 13 VENDOR MANAGED DISTRIBUTION SYSTEMS 2 7 14 TAXI CAB SERVICES 2 8 OBSERVATIONS AND RESEARCH GAP 2 8 1 PROBLEM IN BALANCED LOGISTICS 2 8 2 PROBLEM IN REVERSE LOGISTICS 2 8 3 PROBLEM IN DISTRIBUTION LOGISTICS 2 8 4 PROBLEM IN URGENCY LOGISTICS 2 8 5 COMMON OBSERVATIONS 2 9 REVIEW OF THE VARIANTS OF TSP ADDRESSED IN THIS BOOK 2 9 1 MULTIPLE TRAVELLING SALESMEN PROBLEM 2 9 2 TSP WITH SIMULTANEOUS DELIVERY AND PICK-UP 2 10 REVIEW OF THE VARIANTS OF VRP ADDRESSED IN THIS BOOK 2 10 1 VEHICLE ROUTING PROBLEM WITH BACKHAULS 2 10 2 VRP WITH FORCED BACKHAULS 2 11 SUMMARY 3 ROUTING FOR BALANCED LOGISTICS 3 1 MULTIPLE TRAVELLING SALESMAN PROBLEM WITH WORKLOAD BALANCING 3 2 HEURISTICS TO SOLVE MTWB 3 2 1 RATIONALE BEHIND THE HEURISTICS 3 3 CLUSTERING APPROACH WITH SHRINK-WRAP ALGORITHM FOR MTWB: CASA (H11) 3 3 1 STEP-BY-STEP PROCEDURE OF CASA 3 3 2 SHRINK-WRAP ALGORITHM 3 4 CLUSTERING APPROACH BASED IMPROVEMENT HEURISTIC FOR MTWB: CABI (H12) 3 4 1 PHASE 1: NEW CLUSTERING APPROACH 3 4 2 PHASE 2: HEURISTIC BASED ON 2-OPT FOR ROUTING 3 5 PRUFER NUMBER ENABLED GENETIC ALGORITHMS WITH MIN–MAX FUNCTION FOR MTWB: PEGAM (H13) 3 5 1 EVOLUTION CODE OF GA FOR MTWB 3 5 2 PARAMETER SETTINGS FOR PEGAM 3 5 3 ALGORITHM FOR PEGAM 3 6 COMPUTATIONAL EXPERIMENTS 3 6 1 PERFORMANCE OF HEURISTICS 3 7 CASE STUDY 3 8 SUMMARY CONTENTS 4 ROUTING FOR REVERSE LOGISTICS 4 1 TRAVELLING SALESMAN PROBLEM WITH SIMULTANEOUS DELIVERY AND PICK-UP WITH CONSTRAINED CAPACITY (SDPC) 4 2 MATHEMATICAL PROGRAMMING MODEL TO SOLVE SDPC 4 3 HEURISTICS TO SOLVE SDPC 4 3 1 RATIONALE BEHIND THE HEURISTICS 4 4 EXTENDED BRANCH-AND-BOUND CONSTRUCTION HEURISTIC TO SOLVE SDPC 4 4 1 LOWER BOUNDS 4 4 2 UPPER BOUNDS 4 5 CONSTRUCTION HEURISTIC-BASED GA HEURISTIC FOR SDPC: COGA (H21) 4 5 1 PROCEDURE OF COGA 4 5 2 PARAMETER SETTINGS FOR COGA 4 5 3 ALGORITHM FOR COGA 4 6 CONSTRUCTION HEURISTIC-BASED ENHANCED SA HEURISTIC FOR SDPC: CESA (H22) 4 6 1 PROCEDURE OF CESA 4 6 2 PARAMETER SETTINGS FOR CESA 4 6 3 ALGORITHM FOR CESA 4 7 CONSTRUCTION HEURISTIC-BASED HYBRID GA-ESA HEURISTIC FOR SDPC: COGES (H23) 4 7 1 PROCEDURE OF COGES 4 7 2 PARAMETER SETTINGS FOR COGES 4 7 3 ALGORITHM FOR COGES 4 8 COMPUTATIONAL EXPERIMENTS 4 8 1 PERFORMANCE OF HEURISTICS 4 8 2 DISCUSSION ON RESULTS 4 9 CASE STUDY 4 10 SUMMARY 5 ROUTING FOR DISTRIBUTION LOGISTICS 5 1 MIXED VEHICLE ROUTING PROBLEM WITH BACKHAULS 5 1 1 LOWER BOUND FOR THE PROBLEM 5 1 2 MATHEMATICAL PROGRAMMING MODEL TO SOLVE MVRPB 5 2 HEURISTICS TO SOLVE MVRPB 5 2 1 RATIONALE BEHIND THE HEURISTICS 5 3 CLUSTERING BASED OR-OPT FOR ELITISM HEURISTIC FOR MVRPB—CORE (H31) 5 3 1 CLUSTERING 5 3 2 STEP-WISE DESCRIPTION OF MODI? ED K-MEANS CLUSTERING METHODOLOGY 5 3 3 IMPROVEMENT HEURISTIC 5 4 CHANGE OVER SIMULATED ANNEALING HEURISTIC FOR MVRPB—COSA (H32) CONTENTS 5 5 COMPOSITE GENETIC ALGORITHM WITH LOCAL SEARCH HEURISTIC FOR MVRPB—COGAL (H33) 5 5 1 CHROMOSOME REPRESENTATION 5 5 2 FITNESS FUNCTION FOR EVALUATION 5 5 3 INITIAL POPULATION 5 5 4 SELECTION 5 5 5 CROSSOVER 5 5 6 MUTATION 5 5 7 LOCAL SEARCH 5 5 8 ALGORITHM FOR COGAL 5 6 COMPUTATIONAL EXPERIMENTS 5 6 1 PERFORMANCE OF HEURISTICS 5 7 CASE STUDY 5 7 1 STRUCTURE OF BLOOD BANK SUPPLY CHAIN 5 7 2 BLOOD COLLECTION AND DISTRIBUTION PROBLEM 5 8 SUMMARY 6 ROUTING FOR URGENCY LOGISTICS 6 1 BI-OBJECTIVE VEHICLE ROUTING PROBLEM WITH FORCED BACKHAULS 6 2 HEURISTICS TO SOLVE BVFB 6 2 1 RATIONALE BEHIND THE HEURISTICS 6 3 BASIC SAVINGS ALGORITHM 6 4 MODI? ED SAVINGS HEURISTIC WITH ARC REMOVAL FOR BVFB—MSAR (H41) 6 5 MODI? ED SAVINGS HEURISTIC WITH NODE SWAP FOR BVFB—MSNS (H42) 6 6 BI-OBJECTIVE GENETIC ALGORITHM WITH COMBINED FITNESS FOR BVFB—BIOGA (H43) 6 6 1 CHROMOSOME REPRESENTATION 6 6 2 INITIALISATION OF THE POPULATION 6 6 3 FEASIBILITY OF CHROMOSOMES 6 6 4 EVALUATION OF FITNESS FUNCTION 6 6 5 SELECTION PROCESS 6 6 6 CROSSOVER 6 6 7 MUTATION 6 6 8 ELITIST STRATEGY 6 6 9 TERMINATION CONDITION 6 6 10 ALGORITHM FOR BIOGA 6 7 COMPUTATIONAL EXPERIMENTS 6 7 1 PERFORMANCE OF HEURISTICS 6 8 CASE STUDY 6 9 SUMMARY 7 CONCLUSIONS 7 1 SCOPE FOR FURTHER WORK REFERENCES