Multi-objective Management in Freight Logistics Massimiliano Caramia • Paolo Dell’Olmo Multi-objective Management in Freight Logistics Increasing Capacity, Service Level and Safety with Optimization Algorithms 123 Massimiliano Caramia, PhD Paolo Dell’Olmo, PhD Università di Roma “Tor Vergata” Università di Roma “La Sapienza” Dipartimento di Ingegneria dell’Impresa Dipartimento di Statistica, Probabilità Via del Politecnico, 1 e Statistiche Applicate 00133 Roma Piazzale Aldo Moro, 5 Italy 00185 Roma Italy ISBN 978-1-84800-381-1 e-ISBN 978-1-84800-382-8 DOI 10.1007/978-1-84800-382-8 British Library Cataloguing in Publication Data Caramia, Massimiliano Multi-objective management in freight logistics : increasing capacity, service level and safety with optimization algorithms 1. Freight and freightage - Mathematical models 2. Freight and freightage - Management 3. Business logistics I. Title II. Dell'Olmo, Paolo, 1958- 388'.044'015181 ISBN-13: 9781848003811 Library of Congress Control Number: 2008935034 © 2008 Springer-Verlag London Limited Apart from any fair dealing for the purposes of research or private study, or criticism or review, as permitted under the Copyright, Designs and Patents Act 1988, this publication may only be reproduced, stored or transmitted, in any form or by any means, with the prior permission in writing of the publishers, or in the case of reprographic reproduction in accordance with the terms of licences issued by the Copyright Licensing Agency. Enquiries concerning reproduction outside those terms should be sent to the publishers. The use of registered names, trademarks, etc. in this publication does not imply, even in the absence of a specific statement, that such names are exempt from the relevant laws and regulations and therefore free for general use. The publisher makes no representation, express or implied, with regard to the accuracy of the information contained in this book and cannot accept any legal responsibility or liability for any errors or omissions that may be made. Cover design: eStudio Calamar S.L., Girona, Spain Printed on acid-free paper 9 8 7 6 5 4 3 2 1 springer.com Preface Thecontentofthisbookismotivatedbytherecentchangesinglobalmarketsandthe availabilityofnewtransportationservices.Indeed,thecomplexityofcurrentsupply chainssuggeststodecisionmakersinlogisticstoworkwithasetofefficient(Pareto- optimal)solutions,mainlytocapturedifferenteconomicalaspectsthat,ingeneral, oneoptimalsolutionrelatedtoasingleobjectivefunctionisnotabletocaptureen- tirely. Motivated by these reasons, we study freight transportation systems with a specific focus on multi-objective modelling. The goal is to provide decision mak- erswithnewmethodsandtoolstoimplementmulti-objectiveoptimizationmodels inlogistics.Thebookcombinestheoreticalaspectswithapplications,showingthe advantagesandthedrawbacksofadoptingscalarizationtechniques,andwhenitis worthwhile to reduce the problem to a goal-programming one. Also, we show ap- plications where more than one decision maker evaluates the effectiveness of the logistic system and thus a multi-level programming is sought to attain meaningful solutions.Afterpresentingthegeneralworkingframework,weanalyzelogisticis- suesinamaritimeterminal.Next,westudymulti-objectiverouteplanning,relying on the application of hazardous material transportation. Then, we examine freight distributiononasmallerscale,asforthecaseofgoodsdistributioninmetropolitan areas.Finally,wepresentahuman-workforceproblemarisinginlogisticplatforms. Thegeneral approachfollowedinthetextisthatofpresentingmathematics,algo- rithmsandtherelatedexperimentationsforeachproblem. Rome, MassimilianoCaramia May2008 PaoloDell’Olmo v Acknowledgements TheauthorswishtothankEugeniaCivico,IsabellaLari,AlessandroMassacciand Maria Grazia Mecoli for their contribution in the implementation of the models in Chapter 3; Pasquale Carotenuto, Monica Gentili and Andrea Scozzari for their contribution to the hazmat project to which Chapter 4 refers; Monica Gentili and PituMirchandaniasco-authorsofpreviousworkrelatedtoChapter6. vii Contents ListofFigures ..................................................... xiii ListofTables ...................................................... xv 1 Introduction................................................... 1 1.1 FreightDistributionLogistic ................................. 1 2 Multi-objectiveOptimization.................................... 11 2.1 Multi-objectiveManagement................................. 11 2.2 Multi-objectiveOptimizationandPareto-optimalSolutions ....... 12 2.3 TechniquestoSolveMulti-objectiveOptimizationProblems....... 14 2.3.1 TheScalarizationTechnique........................... 15 2.3.2 ε-constraintsMethod ................................. 18 2.3.3 GoalProgramming................................... 21 2.3.4 Multi-levelProgramming ............................. 22 2.4 Multi-objectiveOptimizationIntegerProblems.................. 25 2.4.1 Multi-objectiveShortestPaths ......................... 27 2.4.2 Multi-objectiveTravellingSalesmanProblem ............ 32 2.4.3 Other Work in Multi-objective Combinatorial OptimizationProblems ............................... 33 2.5 Multi-objectiveCombinatorialOptimizationbyMetaheuristics .... 34 3 MaritimeFreightLogistics ...................................... 37 3.1 CapacityandServiceLevelinaMaritimeTerminal .............. 37 3.1.1 TheSimulationSetting ............................... 40 ix x Contents 3.1.2 TheSimulationModel................................ 43 3.1.3 SimulationResultsAnalysis ........................... 47 3.2 FinalRemarksandPerspectivesonMulti-objectiveScenarios ..... 50 3.3 ContainerAllocationinaMaritimeTerminalandSchedulingof InspectionOperations....................................... 51 3.3.1 ContainersAllocationinaMaritimeTerminal ............ 52 3.3.2 FormulationoftheAllocationModel.................... 54 3.4 SchedulingofCustomsInspections............................ 56 3.5 ExperimentalResults ....................................... 60 4 HazardousMaterialTransportationProblems..................... 65 4.1 Introduction ............................................... 65 4.2 Multi-objectiveApproachestoHazmatTransportation............ 68 4.2.1 TheProblemoftheRiskEquity ........................ 69 4.2.2 TheUncertaintyinHazmatTransportation ............... 70 4.2.3 SomeParticularFactorsInfluencingHazmatTransportation. 71 4.2.4 TechnologyinHazmatTransportation................... 71 4.3 RiskEvaluationinHazmatTransportation...................... 72 4.3.1 RiskModels ........................................ 72 4.3.2 TheTraditionalDefinitionofRisk ...................... 73 4.3.3 AlternativeDefinitionofRisk.......................... 75 4.3.4 AnAxiomaticApproachtotheRiskDefinition ........... 77 4.3.5 QuantitativeAnalysisoftheRisk....................... 78 4.4 TheEquityandtheSearchforDissimilarPaths.................. 80 4.4.1 TheIterativePenaltyMethod .......................... 80 4.4.2 TheGatewayShortest-Paths(GSPs)Method ............. 81 4.4.3 TheMinimaxMethod ................................ 83 4.4.4 The p-dispersionMethod ............................. 84 4.4.5 AComparisonBetweenaMulti-objectiveApproachand IPM ............................................... 87 4.5 TheHazmatTransportationonCongestedNetworks ............. 89 4.5.1 Multi-commodityMinimumCostFlowwithandWithout Congestion ......................................... 91 4.5.1.1 TheModelsFormulation...................... 91 4.5.2 TestProblemsonGridGraphs ......................... 95 Contents xi 4.5.3 TheLinearizedModelwithCongestion.................. 97 4.6 TheProblemofBalancingtheRisk............................ 98 4.6.1 ProblemFormulation................................. 98 4.7 Bi-levelOptimizationApproachestoHazmatTransportation ......100 5 CentralBusinessDistrictFreightLogistic.........................103 5.1 Introduction ...............................................104 5.2 ProblemDescription ........................................105 5.2.1 MathematicalFormulation ............................107 5.3 SolutionStrategies .........................................111 5.3.1 ExperimentalResults.................................112 5.4 Conclusions ...............................................119 6 HeterogeneousStaffSchedulinginLogisticPlatforms ..............121 6.1 Introduction ...............................................121 6.2 TheHeterogeneousWorkforceSchedulingProblem..............126 6.3 ConstraintsandObjectiveFunctionsoftheCHWSP .............126 6.3.1 Constraints .........................................127 6.3.2 ObjectiveFunctions ..................................128 6.4 SimulatedAnnealing:GeneralPresentation.....................131 6.4.1 TheLengthoftheMarkovChains ......................133 6.4.2 TheInitialValueoftheControlParameter ...............134 6.4.3 TheFinalValueoftheControlParameter ................135 6.4.4 DecrementoftheControlParameter ....................135 6.5 OurSimulatedAnnealingAlgorithm ..........................137 6.5.1 ProcedureforDeterminingtheFirstValueoftheControl Parameter ..........................................137 6.5.2 EquilibriumCriterionandStopCriterion ................138 6.5.3 DecrementRulefortheControlParameter ...............138 6.5.4 FunctionPerturb(s →s ) .............................139 i j 6.6 ExperimentalResults .......................................140 6.6.1 PresentationoftheExperimentsandImplementationDetails 140 6.6.2 AnalysisoftheExperiments ...........................141 6.6.3 ComputationalTimes.................................146 6.7 Conclusions ...............................................147 xii Contents AAMPLCode:TheContainer-allocationProblem.....................149 BAMPLCode:TheInspectionSchedulingProblem....................151 CCodeintheCLanguage:TheIterativePenaltyMethodAlgorithm.....153 DCodeintheCLanguage:TheP-DispersionAlgorithm................163 References.........................................................175 Index .............................................................187