Embed Size (px)
Citation preview
Page 1
Modelos y métodos de la distribución de
mercancías
Máster en organización industrial y Gestión de empresas
Trabajo fin de máster
Zoha Ahmadi Danesh
Tutor: Dr. David Canca Ortíz
E.T.S. Ingenieros
Universidad de Sevilla
Page 2
Index
Chapter 1 : Overview in Spanish 8
1. Introducción a la cadena de suministros 8
1.1. Objetivo 9
1.2. Decisiones estratégicas o de diseño 10
1.3. Planificación de la cadena de suministros 11
1.4. Operación de la cadena de suministros 11
1.5. Análisis de las cadenas de suministro 12
1.6. Macro-procesos 15
1.7. Resumen del proyecto. 16
Chapter 2 : Introduction to Supply chain management 17
1. Definition: 17
Chapter 3 : The Supply chain modeling 20
1. The main scope of supply chain modeling 20
2. Key components of supply chain modeling 20
2.1. Supply chain drivers 21
2.2. Supply chain constraints 23
2.3. Supply chain decision variables 24
3. Taxonomies of supply chain modeling 25
Chapter 4 : Introduction to NP, NP-Hard and NP-complete problems 27
1. Classification of problems 27
2. Class P: 28
3. Class NP: 28
4. The relation between P and NP 29
5. NP complete problem 29
5.1. Polynomial-time reducibility 30
5.2. Formal definition of NP complete 31
6. NP-hard problems: 31
7. What can we do about these problems? 31
7.1. Approximation algorithms 33
Page 3
7.2. Polynomial-time approximation schemes 33
7.3. Heuristic algorithms 33
Chapter 5 : Vehicle routing problems (VRP) 34
1. Introduction: 34
2. The travelling salesman problem: 34
3. Vehicle routing problems (VRP): 35
4. Different types of VRP: 37
4.1. Capacitated Vehicle Routing Problem (CVRP) 37
4.2. Single/Multiple depot Vehicle Routing Problem 38
4.3. Vehicle Routing Problem with Time Windows 39
4.4. Vehicle routing problem with pickups and deliveries 40
4.5. Dynamic or Stochastic vehicle routing problem 44
4.6. Periodic Vehicle Routing Problem 48
4.7. Split Delivery Vehicle Routing Problem 49
4.8. Vehicle Routing Problem with Backhauls 51
Chapter 6 : Solution techniques for VRP 52
1. Branch &Bound 52
2. Heuristics 53
2.1. Tour construction heuristics 53
2.2. Tour improvement heuristics 55
2.3. Clark and Wright (1964) 56
3. Metaheuristics 58
3.1. Tabu search: 58
3.2. Simulated annealing 59
3.3. Ant colony optimization 60
3.4. Evolutionary (Genetic) algorithms (or population-based metaheuristics) 63
3.5. Hybrid methods 65
Chapter 7 : Inventory Routing Problem 66
1. Introduction 66
2. Single-period models 68
3. Multi-period models 69
4. Infinite horizon 75
Page 4
5. Stochastic IRP 78
Chapter 8 : The Airline Scheduling Problem 81
1. Introduction: 81
2. Planning Problem: 83
2.1. The crew planning problem 85
Chapter 9 : Case study of a distribution network problem 92
1. Introduction: 92
2. Formulations 92
2.1. Classical model 92
2.2. Three-index model 94
2.3. Original formulation 95
3. Description of a problem 97
3.1. Experimental results 98
4. Conclusions 103
References 104
Page 5
Figures
Figure 1: Cadena de suministros ................................................................................................................ 9
Figure 2: Los procesos en cadena de suministros .................................................................................... 13
Figure 3: Las actividades de Macro procesos .......................................................................................... 16
Figure 4: The Supply chain process. ........................................................................................................ 17
Figure 5: Taxonomy of supply chain management ................................................................................... 26
Figure 6: Diagram of complexity classes provided that P ≠ NP. ............................................................. 29
Figure 7: A solution to Hamilton.s Icosian Game .................................................................................... 34
Figure 8: An example solution to a Vehicle Routing Problem ................................................................ 35
Figure 9: A dynamic vehicle routing scenario with 8 advances and 2 immediate request customers .... 46
Figure 10: Example showing split delivery .............................................................................................. 50
Figure 11: The nearest neighbor heuristic (Bentley 1992) ...................................................................... 54
Figure 12: Examples of Clarke and Wright Saving Heuristic (Fiala 1978)............................................. 57
Figure 13: An experimental setting that demonstrates the shortest path finding capability of ant
colonies. .................................................................................................................................................... 62
Figure 14: An illustration of simple cross-over. ....................................................................................... 64
Figure 15: Related activities in SCM........................................................................................................ 66
Figure 16: Phases and interdependences of the scheduling problem ...................................................... 81
Figure 17: A three duty dates "Madrid" pairing ..................................................................................... 86
Figure 18: Planning for the cockpit slice [1/1/0//0/0/0] .......................................................................... 88
Figure 19: The main graph of the 11 cities .............................................................................................. 97
Figure 20: The reduced graph use in the first two models and their optimal solution ............................ 99
Figure 21: Diagrams showing the changes of computation times by different size of network .............. 102
Page 6
Tables
Table 1: Vehicle Routing Problem classification ..................................................................................... 36
Table 2: The minimum distances between the delivery cities .................................................................. 98
Table 3: Results for the three models in case of 11 cities including 4 demand cities and the capacity of 8
for each vehicle ......................................................................................................................................... 98
Table 4: Results for two models in case of 20 cities including 14 demand cities and the capacity of 8 for
each vehicle ............................................................................................................................................. 100
Table 5: The results of Original model for 26 cities including 19 demand cities and the capacity of 8 for
each vehicle ............................................................................................................................................. 101
Table 6: The results of Original model for 26 cities including 19 demand cities and the capacity of 12
for each vehicle ....................................................................................................................................... 101
Page 7
Goals:
A supply chain is known as a network consist of different facilities and distribution options in order
to procure materials, convert these materials into the intermediate and finished products, and the
distribution of these finished products to the customers.
Supply chain plays important part both in the Service and manufacturing organizations, although the
complexity of the chain may vary greatly from industry to industry or firm to firm.
Supply chain management is a mechanism proposed to integrate all the functions that traditionally
were operating separately, functions like marketing, distribution, planning and manufacturing. As a
result of these changes distribution market has grown rapidly. This caused enterprises to improve their
management and control on their productive system but also caused the delivery service become a very
important part as in internal productivity chain and as for the third part to improve their quality of their
delivery systems.
Actually, big companies use high profile fleet management solutions tailored to their needs: fleet
management and control systems provide information useful to automate goods‘ pickup and delivery
process. So reducing the transport costs and optimize hired resources is of big attention especially for
companies that lead their activities on distributing goods. This is exactly the background from which the
optimization methods and different software are produced to find solutions for solving the problems that
markets are facing now.
Our objective is to provide a brief introduction to Supply chain management. As long as the Supply
chain management is a vast area, this thesis will emphasize on the aspect of operative part focusing on
different distribution and transportation classical models: Vehicle Routing Problem (VRP), Inventory
Routing Problem (IRP) (which combine routing problem with production integration). In addition, for
the importance of Airline Scheduling Problem which now a day play an important part in traveling of
passengers and also in distributing of merchants, and for the difficulties found in these kinds of models
we decided to briefly discuss them in chapter 8.
At the end we will discuss a practical VRP model of delivering goods to customers in different cities,
comparing it with classical and three-index models of the same problem.
Page 8
Chapter 1 : Overview in Spanish
1. Introducción a la cadena de suministros
Una cadena de suministros está formada por todas las partes relacionadas directa o indirectamente
con la satisfacción de una petición de un cliente. La cadena no incluye solamente fabricantes y
suministradores (proveedores) sino también transportistas, almacenes, mayoristas y los propios
clientes.
Dentro de cada organización, por ejemplo un fabricante, la cadena de suministros incluye todas las
funciones involucradas en la recepción y procesado de la petición de un cliente. Entre estas funciones
están: Desarrollo de nuevos productos, Mercadotecnia, Operaciones de producción, Distribución,
finanzas, y atención al cliente.
El cliente es parte esencial en la existencia de la cadena de suministros. El objetivo primordial de
una cadena de suministros es la satisfacción de la necesidad del cliente, generando beneficios para las
distintas partes que la componen. La actividad de una cadena de suministros se inicia con una orden de
un cliente y finaliza cuando el cliente satisfecho paga por su compra.
El término ―cadena de suministros‖ hace referencia al proceso por el cual un producto, materia
prima o componentes (suministro) se va moviendo a lo largo de un conjunto de actores –proveedores a
fabricantes-fabricantes a distribuidores –distribuidores a comercios –comercios a clientes –a lo largo
de una cadena. Es importante reseñar que no sólo se mueven suministros, sino información y capital.
En ambas direcciones de la cadena. Una cadena de suministros es dinámica y contiene todos los flujos
de información, productos y capital entre las diferentes etapas o actores.
Obviamente un fabricante puede recibir material de varios proveedores y servir a distintos
distribuidores. Realmente las cadenas de suministros se entrelazan formando redes. Tal vez sea más
conveniente usar el términos redes de suministro.
Page 9
Figure 1: Cadena de suministros
Normalmente una cadena de suministros incluye los actores mencionados ya: Proveedores-
Fabricantes -Distribuidores -minoristas (Comercios) y Clientes -. Sin embargo no siempre estarán
presentes todos los actores.
1.1. Objetivo
El objetivo de toda cadena de suministros es maximizar el valor generado global. El valor
generado es la diferencia entre lo que el cliente paga por un producto y el esfuerzo que la cadena
gasta en satisfacer los deseos del cliente.
Para la mayoría de las cadenas de suministros comerciales, el valor generado está
íntimamente correlacionado con el beneficio que se obtiene por producto a lo largo de la cadena.
Este beneficio es la diferencia entre el pago del cliente y los costes generados a lo largo de toda la
cadena para poder atender el servicio de ese producto concreto.
Todos los flujos de productos (materias primas, componentes o productos), información y
dinero generan costes dentro de la cadena. La Gestión de la cadena de suministros se centra en la
gestión de los flujos entre las diferentes etapas de manera que se maximice el beneficio de la
global de la misma.
Page 10
El beneficio por producto de la cadena es el beneficio total que debe ser compartido a lo
largo de la misma por todos sus componentes. A mayor beneficio por producto mayor es el éxito
de la cadena. La cadena debe ser medida por el beneficio global y no por el de cada una de sus
partes.
Un esfuerzo por aumentar los beneficios en determinadas etapas de la cadena puede llevar
a una disminución global de los beneficios obtenidos por la misma.
El éxito de una cadena de suministros requiere de la toma de decisiones en relación con el
flujo de materiales, monetario y de información. Estas decisiones se pueden agrupar en tres
categorías o etapas dependiendo de la frecuencia con que deben ser tomadas y intervalo de
tiempo en el que se refleja el impacto de las mismas:
1.2. Decisiones estratégicas o de diseño
En esta etapa una compañía decide como estructurar su cadena de suministro durante los
próximos años. Se definirá la estructura o configuración de la cadena, los recursos necesarios y
los procesos que se deben desarrollar en cada eslabón.
Decisiones estratégicas son:
--La localización y capacidad de las instalaciones de producción y almacenamiento.
--La asignación de productos que serán fabricados o almacenados en cada localización
(piénsese en la decisión de qué modelo de vehículo va a ser desarrollado o de qué modelo de
avión se va a construir y dónde –en que centro o factoría –se soportará el peso de la producción).
--Los modos de transporte que deben emplearse en cada uno de los puntos de envío (en
cada una de las instalaciones).
--Los sistemas de información que deben emplearse en cada una de las etapas (mejor, en la
relación de la firma con los demás componentes de la cadena).
Las decisiones estratégicas se toman de forma habitual para largos períodos de tiempo
(largo plazo). Estas decisiones involucran inversiones grandes y su impacto es tan grande que no
pueden ser alteradas en corto espacio de tiempo pues esto supondría elevadas pérdidas. Cuando
una compañía toma este tipo de decisiones debe tener en cuenta la incertidumbre propia del
mercado en los próximos años.
Page 11
1.3. Planificación de la cadena de suministros
Las decisiones tomadas en esta etapa tienen un horizonte temporal de varios meses (de 3 a
6 meses). La configuración de la cadena de suministros definida en la etapa de diseño
(estratégica) permanece fija.
Esta configuración impone condiciones que deben ser consideradas en esta etapa. Las
decisiones de tipo táctico comienzan con una previsión de la demanda (normalmente para el
próximo año) para sus diferentes mercados.
Las decisiones tácticas incluyen:
--Que mercados van a ser atendidos desde cada una de las instalaciones de la compañía.
--Cantidades globales que se deberán producir o subcontratar y la propia decisión de
producir o subcontratar la producción.
--Que políticas de inventario deben ser seguidas.
--Horizonte y envergadura de las campañas de marketing y promoción
Dado que son decisiones que se toman en un período de tiempo más corto que en la fase de
diseño y puesto que las predicciones a corto plazo disminuyen la incertidumbre, las compañías
tratan de explotar toda flexibilidad de la cadena de suministros y explotarlas para optimizar su
funcionamiento.
1.4. Operación de la cadena de suministros
El horizonte temporal es ahora semanal o diario. En esta etapa las compañías toman
decisiones referentes a órdenes individuales de clientes. La configuración de la cadena es fija y
las decisiones o políticas de planificación de la compañía se deben respetar.
Decisiones operacionales:
--Ajustar producción e inventarios a las órdenes individuales de los clientes.
-- Determinar la fecha en que una orden debe ser servida.
-- Generar las listas de productos que deben ser atendidas en almacén o almacenes –
Picking orders-.
Page 12
--Asignar cada orden a un método de transporte.
--Preparar el ―scheduling‖(Programación temporal y secuencia) de los transportes para las
órdenes que van a ser servidas.
--Realizar los transportes de los productos.
--Lanzar las correspondientes órdenes de reposición.
Puesto que el horizonte temporal es corto, la incertidumbre sobre la demanda es pequeña.
1.5. Análisis de las cadenas de suministro
Una cadena de suministros es una secuencia de procesos y flujos (Monetario, Información
y Productos) que tienen lugar dentro y entre cada uno de los componentes que trabajan para
satisfacer las necesidades de los clientes.
Los procesos que tienen lugar a lo largo de la cadena se pueden analizar desde dos puntos
de vista:
1.5.1. Vista de ciclos
Los procesos que suceden en la cadena se analizan en forma de un conjunto de ciclos, cada
uno de ellos transcurre en la interacción entre dos componentes.
Los procesos que tienen lugar en la cadena se dividen en cuatro ciclos:
1. De cliente
2. De reposición
3. De fabricación
4. De aprovisionamiento
Estos ciclos no siempre se producen de forma separada y no siempre están presentes.
Esta forma de ver la cadena de suministros es muy útil cuando se consideran decisiones
operacionales ya que se especifican claramente los roles y responsabilidades de cada uno de
los miembros.
Page 13
Figure 2: Los procesos en cadena de suministros
Ciclo de cliente
Entre minorista (comercio) y cliente: El cliente inicia el ciclo en la instalación del comercio y
normalmente el ciclo conlleva la satisfacción de la orden o necesidad del cliente.
o Llegada del cliente
Hace referencia al instante en que el cliente accede a las instalaciones del minorista, realiza
una llamada o envía un mail a una firma de tele comercio o usa la web para realizar un
pedido. El objetivo del proceso es maximizar la conversión de llegadas de clientes en
pedidos.
o Entrada de la orden del cliente
Se refiere al proceso por el cual el cliente informa al comerciante de que producto desea y el
comerciante localiza los productos para su cliente.
El objetivo del proceso consiste en garantizar que la petición del cliente se realiza de forma
rápida, precisa y en comunicar la información a los demás procesos de la cadena que se ven
afectados.
o Ejecución de la orden
Page 14
Durante este proceso, la orden del cliente se procesa. Los inventarios del minorista deben ser
restablecidos, lo que con frecuencia se traduce en la aparición de órdenes de reposición,
inicio del ciclo de reposición.
En general este proceso se realiza a partir de los inventarios de los minoristas. En el caso de
fabricación bajo pedido (industria de automoción, naval, aeronáutica), el proceso se realiza
directamente en la línea de producción de fabricante. El objetivo de este proceso es el envío
de los productos a los clientes, en las fechas prometidas con el menor coste posible.
o Recepción de la orden
El cliente recibe el envío y toma posesión del producto. En determinadas situaciones se
puede completar el registro de esa recepción y completar el pago del producto.
Ciclo de reposición
Entre comerciante y distribuidor. Se inicia cuando el comerciante lanza una orden para reponer
productos en su inventario con el objeto de satisfacer una demanda futura. Es un ciclo similar al
de cliente sólo que ahora el cliente es el minorista. El objetivo es la reposición de inventarios a
mínimo coste garantizando la máxima disponibilidad de productos. El ciclo de reposición se ve
afectado con la incertidumbre propia de las órdenes de los clientes finales.
o Disparo de orden de reposición.
El objetivo cuando se lanzan órdenes de reposición es maximizar los beneficios asegurando
economías de escala y balanceando la disponibilidad en inventario frente a los costes de
mantenimiento en stock.
o Entrada de orden de reposición.
Traslado de la orden de reposición desde el minorista al distribuidor. El objetivo del proceso
es garantizar la rapidez en la transferencia e la orden y la exactitud de la misma.
o Ejecución de la orden de reposición.
o Recepción de la orden de reposición.
Ciclo de fabricación
Ocurre entre distribuidor y fabricante, minorista y fabricante ya veces entre cliente y fabricante.
Se dispara como consecuencia de una petición de quien hace las veces de cliente (Distribuidor,
minorista o cliente final). Es consecuencia de la ejecución de una orden directa por parte de
cliente (caso Dell) de reposición por parte del distribuidor o del minorista o de la estimación de
demanda de productos de clientes finales y de la disponibilidad de productos en los almacenes de
productos del fabricante.
o Llegada de la orden
o Planificación de la producción
Page 15
o Fabricación y distribución
o Recepción de mercancías
Ciclo de aprovisionamiento
Ocurre entre fabricante y proveedor e incluye todos los procesos necesarios para asegurar que las
materias primas y componentes están disponibles para que la fabricación se realice de acuerdo a
lo planificado. Los fabricantes lanzan orden de reposición de componentes a sus proveedores.
Las órdenes lanzadas responden de forma precisa a la planificación diseñada por el fabricante.
1.5.2. Vista Push/Pull:
Los procesos se dividen en dos categorías dependiendo si tienen lugar como respuesta a la
orden de un cliente (modo respuesta-Pull) o de forma anticipada a estas (modo anticipado o
Push).
Todos los procesos que tienen lugar en una cadena de suministros se pueden clasificar en
dos categorías dependiendo de la forma de ejecución respecto a la demanda de los clientes.
Los procesos tipo pull (Respuesta) se ejecutan como respuesta a la orden de un cliente. A la
hora de la ejecución de un proceso tipo respuesta, la demanda es conocida con certeza,
mientras que en el caso de procesos en modo anticipado la demanda debe ser estimada. Por
este motivo los procesos tipo push se denominan especulativos (predictivos o estimativos).
Un análisis Push/Pull es interesante cuando se analizan decisiones de tipo estratégico
relacionadas con el diseño de la cadena de suministros.
1.6. Macro-procesos
Todos los procesos de una cadena de suministros para una determinada compañía se
pueden incluir dentro de tres grandes Macro-procesos:
1. Gestión de relaciones con los clientes. Customer Relationship Management (CRM).
2. Gestión interna de la cadena de suministros. Internal Supply Chain Management
(ISCM).
3. Gestión de la relaciones con proveedores. Supplier Relationship Management (SRM).
La siguiente figura muestra las actividades propias de cada uno de estos macro procesos.
Page 16
Figure 3: Las actividades de Macro procesos
1.7. Resumen del proyecto.
El presente trabajo final de master pretende desarrollar una breve introducción al concepto
de cadena de suministros, centrándose en algunos aspectos de tipo operativo, exponiendo la
literatura más relevante al efecto y revisando los modelos clásicos relacionados con distribución y
transporte de mercancías: Vehicle Routing Problem, Inventory Routing Problem (que combina el
problema de selección de rutas con el de reaprovisionamiento de productos).
Nos ha parecido interesante, dada la relevancia del transporte aéreo de pasajeros para viajes
a larga distancia y la cada vez mayor influencia de este modo en el transporte de mercancías así
como la dificultad de la gestión de este modo de transporte, incluir en el capítulo 8, Airline
Scheduling Problem, una revisión de los modelos asociados al transporte aéreo.
El último capítulo presenta una aplicación práctica. Se ha desarrollado un modelo para
analizar el reparto de mercancías a distintos ciudades, considerando restricciones de capacidad y
flujos propios y la comparación de este modelo con dos otros modelos VRP, el modelo clásico y
el modelo tres-índices.
Page 17
Chapter 2 : Introduction to Supply chain management
1. Definition:
A supply chain is referred to as an integrated system which synchronizes a series of inter-related
business processes in order to: (1) acquire raw materials and parts; (2) transform these raw materials
and parts into finished products; (3) add value to these products; (4) distribute and promote these
products to either retailers or customers; (5) facilitate information exchange among various business
entities (e.g. suppliers, manufacturers, distributors, third-party logistics providers, and retailers). Its
main objective is to enhance the operational efficiency, profitability and competitive position of a firm
and its supply chain partners. Supply chain management is defined as `the integration of key business
processes from end-users through original suppliers that provide products, services, and information
and add value for customers and other stakeholders' (Cooper, Lambert, & Pagh, 1997). A supply chain
is characterized by a forward flow of goods and a backward flow of information as shown by Fig 4.
Figure 4: The Supply chain process.
In current distribution networks the flow of goods between a supplier and a customer often passes
through several stages or echelons. In such a supply chain each stage may comprise many facilities.
These perform many different activities and their mutual coordination requires intensive
Suppliers CustomersRetailersDistributorsManufacturers
Third Party Logistics Providers
Inbound Logistics
Material Management
Outbound Logistics
Physical Distribution
Flow of information
Flow of goods
Page 18
communication. For example, stocks need replenishing, deliveries need routing and orders need
picking.
Due to intensive competition in global markets, logistic supply chain performance is considered an
important strategic weapon to achieve and maintain competitive strength. The design or redesign of
large-scale distribution networks entails taking decisions on a range of issues, including the location
and size of distribution centers, the logistic activities to be performed at these centers, the capacities
required to fulfill these activities, their allocation to specific product groups, and the control system to
manage all activities. These activities include transport, consolidation, transshipment, maintenance of
the inventory, and the assembly or reconditioning of products. Furthermore, there is a growing need
for contingency plans to help logistic systems cope with disruptions.
In today's global marketplace, individual firms no longer compete as independent entities with
unique brand names, but rather as integral part of supply chain links. As such, the ultimate success of a
firm will depend on its managerial ability to integrate and coordinate the intricate network of business
relation-ships among supply chain members (Drucker, 1998; Lambert & Cooper, 2000).
Typically, a supply chain is comprised of two main business processes:
o Material management (inbound logistics)
o Physical distribution (outbound logistics)
Material management is concerned with the acquisition and storage of raw materials, parts, and
supplies. To elaborate, material management supports the complete cycle of material flow from the
purchase and internal control of production materials to the planning and control of work-in-process,
to the warehousing, shipping, and distribution of finished products (Johnson & Malucci, 1999).
On the other hand, physical distribution encompasses all outbound logistics activities related to
providing customer service. These activities include order receipt and processing, inventory
deployment, storage and handling, outbound transportation, consolidation, pricing, promotional
support, returned product handling, and life-cycle support (Bowersox & Closs, 1996). Combining the
activities of material management and physical distribution, a supply chain does not merely represent a
linear chain of one-on-one business relationships, but a web of multiple business networks and
Page 19
relationships. Along a supply chain, there may be multiple stakeholders comprised of various
suppliers, manufacturers, distributors, third-party logistics providers, retailers, and customers.
Page 20
Chapter 3 : The Supply chain modeling
1. The main scope of supply chain modeling
Considering the broad spectrum of a supply chain, no model can capture all aspects of supply chain
processes. To compromise the dilemma between model complexity and reality, a model builder should
define the scope of the supply chain model in such a way that it is reflective of key real-world
dimensions, yet not too complicated to solve. Although it‘s hard to have a specific plan for the scope
of a `firm specific' supply chain problem, it may follow a simple guideline proposed by Chopra and
Meindl (2001) and Stevens (1989). This guideline is based on the three levels of decision hierarchy:
(1) competitive strategy; (2) tactical plans; (3) operational routines. The classes of supply chain
problems encountered in competitive strategic analysis include location-allocation decisions; demand
planning, distribution channel planning, strategic alliances, new product development, outsourcing,
supplier selection, information technology (IT) selection, pricing, and network restructuring. Although
most supply chain issues are strategic by nature, there are also some tactical problems. These include
inventory control, production/distribution coordination, order/freight consolidation, material handling,
equipment selection, and layout design. The problems encountered when dealing with operational
routines include vehicle routing/scheduling, workforce scheduling, record keeping, and packaging. It
should be noted that the aforementioned distinctions are not always clear, because some supply chain
problems may involve hierarchical, multi-echelon planning that overlap different decision levels.
Regardless, such a guideline would help a model builder determine the breadth of the problem
scope and the length of supply chain planning horizons.
Another guideline to follow is the three structures of a supply chain network suggested by Cooper
et al. (1997). These structures are: (1) the type of a supply chain partnership; (2) the structural
dimensions of a supply chain network; (3) the characteristics of process links among supply chain
partners.
2. Key components of supply chain modeling
For establishing Supply chain goals it is important to know the key component of a supply chain.
Absence of specific goals, in turn, means difficulty in developing appropriate performance measures
that can be targeted or benchmarked by a supply chain partner. Since a performance measure dictates
Page 21
the desired outcome of the supply chain model, it is very important for a model builder to identify key
components of a supply chain. Although those components may differ from one company to another,
we offer some examples of those.
2.1. Supply chain drivers
Goal setting will be the first step of supply chain modeling. To set the supply chain goals, a
model builder first needs to figure out what will be the major driving forces (drivers) behind the
supply chain linkages. These drivers include customer service initiatives, monetary value,
information/knowledge transactions, and risk elements.
Customer service initiatives
Though difficult to quantify, the ultimate goal of a supply chain is customer satisfaction.
Put simply, customer satisfaction is the degree to which customers are satisfied with the
product and/or service received. The following list represents typical service elements in a
supply chain.
o Product availability
Due to random fluctuations in the demand pattern, downstream supply chain
members often fail to meet the real-time needs of customers. Thus, a supply chain
model should reflect service performance measures such as inventory days of supply,
an order fill rate (a percentage of customer orders that were filled on time), and an
`order-accuracy' rate (a percentage of items delivered in the right quantities, complete
documentation, and correct configurations required by customers).
o Response time
Response time represents an important indicator of the supply chain flexibility. Examples
of response time include time-to-market, on-time delivery (a percentage of a match between
the promised product delivery date and the actual product delivery date), order processing time
Page 22
(the amount of time required from the time an order is placed until the time the order is
received by the customer), transit time (duration between the time of shipment and the time of
receipt), cash-to-cash cycle time (the amount of time required from the time a product has
begun its manufacturing until the time it is completely sold and this metric is an indicator of
how quickly customers pay their bills), and downtime (a percentage of time resources that are
not operational due to maintenance and repair).
Monetary value
The monetary value is generally defined as a ratio of revenue to total cost. A supply chain
can enhance its monetary value through increasing sales revenue, market share, and labor
productivity, while reducing expenditures, defects, and duplication. Since such value directly
reflects the cost efficiency and profitability of supply chain activities, this is the most widely
used objective function of a supply chain model.
Information/knowledge transactions
Information serves as the connection between the various phases of a supply chain,
allowing supply chain partners to coordinate their actions and increase inventory visibility
(Chopra & Meindl, 2001). Therefore, successful supply chain integration depends on the
supply chain partners' ability to synchronize and share `real-time' information. Such
information encompasses data, technology, know-how, designs, specifications, samples, client
lists, prices, customer profiles, sales forecasts, and order history.
Risk elements
The important leverage gained from the supply chain integration is the mitigation of risk.
In the supply chain framework, a single supply chain member does not have to stretch beyond
its core competency, since it can pool the resources shared with other supply chain partners. On
the other hand, a supply chain can pose greater risk of failure due to its inherent complexity
Page 23
and volatility. Braithwaite and Hall (1999) noted that a supply chain would be a veritable hive
of risks, unless information is synchronized, time is compressed, and tensions among supply
chain members are recognized. They also observed that supply chain risks (emanating from
external sources to the firm) would be always greater than risks which arose internally, as less
was known about them. Thus, a model builder needs to profile the potential risks involved in
supply chain activities.
2.2. Supply chain constraints
Supply chain constraints represent restrictions (or limitations) placed on a range of decision
alternatives that the firm can choose. Thus, they determine the feasibility of some decision
alternatives. These constraints include:
Capacity:
The supply chain member's financial, production, supply, and technical (EDI or bar
coding) capability determines its desired outcome in terms of the level of inventory,
production, workforce, capital investment, outsourcing, and IT adoption. This capacity also
includes the available space for inventory stocking and manufacturing.
Service compliance:
Since the ultimate goal of a supply chain is to meet or exceed customer service
requirements, this may be one of the most important constraints to satisfy. Typical examples
are delivery time windows, manufacturing due dates, maximum holding time for backorders,
and the number of driving hours for truck drivers.
The extent of demand:
The vertical integration of a supply chain is intended to balance the capacity of supply at
the preceding stage against the extent of consumption (i.e. demand) of the downstream supply
Page 24
chain members at the succeeding stage. Thus, this constraint can be added to the supply chain
model.
2.3. Supply chain decision variables
Since decision variables generally set the limits on the range of decision outcomes, they are
functionally related to supply chain performances. Thus, the performance measures (or objectives)
of a supply chain are generally expressed as functions of one or more decision variables. Though
not exhaustive, the following illustrates these decision variables:
Location:
This type of variable involves determining where plants, warehouses (or distribution
centers (DCs)), consolidation points, and sources of supply should be located.
Allocation:
This type of variable determines which warehouses (or DCs), plants, and consolidation
points should serve which customers, market segments, and suppliers.
Network structuring:
This type of variable involves centralization or decentralization of a distribution network
and determines which combination of suppliers, plants, warehouses, and consolidation points
should be utilized or phased-out. This type of variable may also involve the exact timing of
expansion or elimination of manufacturing or distribution facilities.
Number of facilities and equipment:
This type of variable determines how many plants, warehouses, and consolidation points
are needed to meet the needs of customers and market segments. This type of variable may also
determine how many lift trucks are required for material handling.
Number of stages (echelons):
Page 25
This variable determines the number of stages that will comprise a supply chain. This
variable may involve either increasing or decreasing the level of horizontal supply chain
integration by combining or separating stages.
Service sequence:
This variable determines delivery or pickup routes and schedules of vehicles serving
customers or suppliers.
Volume:
This variable includes the optimal purchasing volume, production, and shipping volume
at each node (e.g. a supplier, a manufacturer, a distributor) of a supply chain.
Inventory level:
This variable determines the optimal amount of every raw material, part, work-in-
process, finished product and stock-keeping unit (SKU) to be stored at each supply chain stage.
Size of workforce:
This variable determines the number of truck drivers or order pickers needed for the system.
The extent of outsourcing:
This type of variable determines which suppliers, IT service providers, and third-party
logistics providers should be used for long-term outsourcing contacts and how many (e.g.
single versus multiple sourcing) of those should be utilized.
3. Taxonomies of supply chain modeling
We can classify supply chain models into four major categories: (1) deterministic (non-
probabilistic); (2) stochastic (probabilistic); (3) hybrid; (4) IT-driven.
Deterministic models assume that all the model parameters are known and fixed with certainty,
whereas stochastic models take into account the uncertain and random parameters. Deterministic
models are dichotomized as single objective and multiple objective models. This category was
developed to reflect the increasing need to harmonize conflicting objectives of different supply chain
Page 26
partners. Stochastic models are sub-classified into optimal control theoretic and dynamic programming
models. Notice that we excluded the categories of decision analysis and queuing models from
stochastic models, because the literature indicates that supply chain models rarely used such
techniques.
Hybrid models have elements of both deterministic and stochastic models. These models include
inventory-theoretic and simulation models that are capable of dealing with both certainty and
uncertainty involving model parameters.
Shapiro (2001) recently observed that IT development was the major driving force for supply chain
innovations and the subsequent reengineering of the business process. Considering the proliferation of
IT applications for supply chain modeling, we decided to add the category of IT-driven models to the
taxonomy. IT-driven models aim to integrate and coordinate various phases of supply chain planning
on real-time basis using application software so that they can enhance visibility throughout the supply
chain. These models include warehousing management systems (WMS), transportation management
systems (TMS), integrated transportation tracking, collaborative planning and forecasting
replenishment (CPFR), material requirement planning (MRP), distribution resource planning (DRP),
enterprise resource planning (ERP), and geographic information systems (GIS).
Figure 5: Taxonomy of supply chain management
Supply Chain Modeling
Deterministic Models IT-Driven ModelsHybrid ModelsStochastic Models
Single Objective
SimulationInventory Theoretic
Dynamic Programming
Optimal Control Theory
Multiple Objective
GISERPWMS
Page 27
Chapter 4 : Introduction to NP, NP-Hard and NP-complete problems
As long as all the problems we may discuss are classified in the computational complexity theory as
NP or NP-Hard or NP complete, we first introduce these kinds of problems in this chapter.
1. Classification of problems
As we have discussed, in the models, one basically try to solve two kinds of problems:
Decision problems
Optimization problems
In decision problems we are trying to decide whether a statement is true or false. In optimization
problems we are trying to find the solution with the best possible score according to some scoring
scheme. Optimization problems can be either maximization problems, where we are trying to
maximize a certain score, or minimization problems, where we are trying to minimize a cost function.
Example of decision problems:
Given a directed graph, we want to decide whether or not there is a Hamiltonian cycle
(A Hamiltonian cycle, Hamiltonian circuit, is a cycle that visits each vertex exactly once
except the vertex which is both the start and end, and so is visited twice) in this graph.
Example of optimization problem:
Traveling salesman problem (TSP) a complete graph with an assignment of weights to
the edges, we have to find a Hamiltonian cycle of minimum weight. This is the optimization
version of the problem but we can convert it to a decision problem if in a given weighted
complete graph and a real number c, we find whether or not there exists a Hamiltonian cycle
whose combined weight of edges does not exceed c,(H,c).
Therefore we can conclude that each optimization problem has a corresponding decision problem.
Page 28
Each of the problems discussed above has its characteristic input. For example, for the optimization
version of the TSP, the input consists of a weighted complete graph; for the decision version of the
TSP, the input consists of a weighted complete graph and a real number. The input data of a problem
are often called the instance of the problem. Each instance has a characteristic size; which is the
amount of computer memory needed to describe the instance. If the instance is a graph of n vertices,
then the size of this instance would typically be about n(n-1)/2.
In computational complexity theory these problems have been classified upon their characteristic.
In following sections we describe the most important ones.
2. Class P:
The complexity class of decision problems that can be solved on a deterministic sequential machine
in polynomial time is known as P. The formal definition is:
A decision problem D is solvable in polynomial time or in the class P, if there exists an algorithm A
such that
A takes instances of D as inputs.
A always outputs the correct answer ―Yes‖ or ―No‖.
There exists a polynomial p such that the execution of A on inputs of size n always
terminates in p(n) or fewer steps.
Note that if the answer to a decision problem is ―yes‖, then there is usually some ―witness‖ to this.
For example, in the Hamiltonian cycle problem, any permutation v1, v2, … ,vn of the vertices of the
input graph is a potential witness. This potential witness is a true witness if v1 is adjacent to v2 , …
and vn is adjacent to v1 and in the TSP, a potential witness would be a Hamiltonian cycle. This
potential witness is a true witness if its cost is c or less.
3. Class NP:
The class of decision problems that can be verified in polynomial time is known as NP.
Equivalently, NP is the class of decision problems that can be solved in polynomial time on a non-
deterministic Turing machine (NP does not stand for "non-polynomial". NP stands for
Nondeterministic Polynomial time). The formal definition is:
Page 29
A decision problem is nondeterministically polynomial-time solvable or in the class NP if there
exists an algorithm A such that
A takes as inputs potential witnesses for ―yes‖ answers to problem D.
A correctly distinguishes true witnesses from false witnesses.
There exists a polynomial p such that for each potential witnesses of each instance of size
n of D, the execution of the algorithm A takes at most p(n) steps.
Note that if a problem is in the class NP, then we are able to verify ―yes‖-answers in polynomial
time, provided that we are lucky enough to guess true witnesses.
4. The relation between P and NP
The most famous open problem in theoretical science is whether P = NP. In other words, if it's
always easy to check a solution, should it also be easy to find the solution?
It is not hard to show that every problem in P is also in NP, but it is unclear whether every problem
in NP is also in P. The best we can say is that thousands of computer scientists have been unsuccessful
for decades to design polynomial-time algorithms for some problems in the class NP.
Figure 6: Diagram of complexity classes provided that P ≠ NP.
5. NP complete problem
In computational complexity theory, the complexity class NP-complete, also known as NP-C or
NPC, is a subset of NP ("non-deterministic polynomial time"); they are the most difficult problems in
NP in the sense that a deterministic, polynomial-time solution to any NP-complete problem would
provide a solution to every other problem in NP (and conversely, if any one of them provably lacks a
deterministic polynomial-time solution, none of them has one). Problems in the class NP-complete are
known as NP-complete problems.
Page 30
5.1. Polynomial-time reducibility
In computability theory and computational complexity theory, a reduction is a transformation of
one problem into another problem. Depending on the transformation used this can be used to
define complexity classes on a set of problems.
Intuitively, problem A is reducible to problem B, if solutions to B exist and give solutions to A
whenever A has solutions. Thus, solving A cannot be harder than solving B. We write A ≤ B,
usually with a subscript on the ≤ to indicate the type of reduction being used.
In computational complexity theory a polynomial-time reduction is a reduction which is
computable by a deterministic Turing machine in polynomial time. The formal definition is:
Let E and D be two decision problems. We say that D is polynomial-time reducible to E if
there exists an algorithm A such that
A takes instances of D as inputs and always outputs the correct answer ―Yes‖ or ―No‖ for
each instance of D.
A uses as a subroutine a hypothetical algorithm B for solving E.
There exists a polynomial p such that for every instance of D of size n the algorithm A
terminates in at most p(n) steps if each call of the subroutine B is counted as only m
steps, where m is the size of the actual input of B.
I. An example of polynomial-time reducibility
Theorem: The Hamiltonian cycle problem is polynomial-time reducible to the decision
version of TSP.
Proof: Given an instance G with vertices v1 , … , vn of the Hamiltonian cycle problem, let
H be the weighted complete graph on v1 , … , vn such that the weight of an edge {vi , vj } in H is
1 if {vi , vj } is an edge in G, and is 2 otherwise. Now the correct answer for the instance G of the
Hamiltonian cycle problem can be obtained by running an algorithm on the instance (H,n+1) of
the TSP.
Page 31
5.2. Formal definition of NP complete
A decision problem E is NP-complete if every problem in the class NP is polynomial-time
reducible to E. The Hamiltonian cycle problem, the decision versions of the TSP and the graph
coloring problem, as well as literally hundreds of other problems are known to be NP-complete. It
is not hard to show that if a problem D is polynomial-time reducible to a problem E and E is in the
class P, then D is also in the class P. It follows that if there exists a polynomial-time algorithm for
the solution of any of the NP-complete problems, then there exist polynomial-time algorithms for
all of them, and P= NP.
6. NP-hard problems:
NP-hard (nondeterministic polynomial-time hard), in computational complexity theory, is a class of
problems informally "at least as hard as the hardest problems in NP."
A problem H is NP-hard if and only if there is an NP-complete problem L that is polynomial time
Turing-reducible to H, i.e. In other words, L can be solved in polynomial time by an oracle machine
with an oracle for H. Informally we can think of an algorithm that can call such an oracle machine as
subroutine for solving H, and solves L in polynomial time if the subroutine call takes only one step to
compute. NP-hard problems may be of any type: decision problems, search problems, optimization
problems.
Optimization problems whose decision versions are NP-complete are called NP-hard.
In view of the overwhelming empirical evidence against the equality P= NP it seems that no NP-
hard optimization problem is solvable by an algorithm that is guaranteed to:
run in polynomial time and
always produce a solution with optimal score/cost.
Unfortunately, many, perhaps most, of the important optimization problems in many engineering
fields are NP-hard. To make matters worse, the instances of real interest in engineering are typically of
large size.
7. What can we do about these problems?
These NP-complete problems really come up all the time. There are some methods to solve these
kinds of problems which we will briefly describe as follow:
Page 32
Use a heuristic:
If it is not possible to solve the problem in reasonable time, it may use a method to
solve a reasonable fraction of the common cases.
Solve the problem approximately instead of exactly:
A lot of the time it is possible to come up with a provably fast algorithm, that doesn't
solve the problem exactly but comes up with a solution you can prove is close to right.
Use an exponential time solution anyway:
If you really have to solve the problem exactly, you can settle down to writing an
exponential time algorithm and stop worrying about finding a better solution.
Choose a better abstraction:
The NP-complete abstract problem you're trying to solve presumably comes from
ignoring some of the seemingly unimportant details of a more complicated real world
problem. Perhaps some of those details shouldn't have been ignored, and make the
difference between what you can and can't solve.
So far we have been talking about algorithms that run in polynomial time on all instances always
find the solution with the best score/cost.
As we have seen, such algorithms may be too much to ask for. We will now briefly discuss how
one can meaning fully relax the above requirements.
So far, we have been insisting that there exists a polynomial p such the running time of an
algorithm is bounded by p(n) for all instances of size n. However, for many practical purposes, it may
be sufficient to have an algorithm whose average running time for an instance of size n is bounded by
a polynomial. Such an algorithm may still be unacceptably slow for some particularly bad instances,
but such bad instances will necessarily be very rare and may be of little practical relevance. Here are
some of algorithms which we may use:
Page 33
7.1. Approximation algorithms
While optimal solutions to optimization problems are clearly best, ―reasonably‖ good solutions
are also of value. Let us say that an algorithm for a minimization problem D has a performance
guarantee of 1 + ε if for each instance I of the problem it finds a solution whose cost is at most (1
+ ε) times the cost of the optimal solution for instance I. While D may be NP-hard, it may still be
possible to find, for some ε > 0, polynomial-time algorithms for D with performance guarantee 1
+ε. Such algorithms are called approximation algorithms. For maximization problems, the notion
of an approximation algorithm is defined similarly.
7.2. Polynomial-time approximation schemes
We say that a minimization problem D has a polynomial-time approximation scheme (PTAS) if
for every ε > 0 there exists a polynomial-time algorithm for D with performance guarantee 1 + ε.
While D may be NP-hard, it may still be have a PTAS.
7.3. Heuristic algorithms
Quite often, engineers rely on heuristic algorithms for solving NP-hard optimization problems.
These are algorithms that appear to run reasonably fast on the average instance, appear to find,
most of the time, solutions within (1 + ε) of optimum for reasonably small ε.
However, it is not always easy or possible to mathematically analyze the performance of a
heuristic algorithm.
As I have mentioned before in this thesis we will go through the operational Vehicle Routing
Problems and Inventory routing problem. In addition we will briefly discuss the Airline scheduling
problem. All these play important parts in Supply chain management.
Page 34
Chapter 5 : Vehicle routing problems (VRP)
1. Introduction:
Interest in the Vehicle Routing Problem (VRP) grew rapidly after World War II, following the
increase in postal traffic and catalog ordering of goods from a remote retailer. VRP falls under a
broader category of transportation problems, which also include fleet management, facility location,
traffic assignment, air traffic control etc.(Gendreau M., J. Potvin. (1998))
Vehicle Routing Problem has a historical and theoretical background in the Traveling Salesman
Problem; both of these address the problem of finding a minimal cost route within a predefined set of
points, given a set of constraints. Minimal cost route is usually described as the shortest route in terms
of Euclidean distance.
2. The travelling salesman problem:
The Traveling Salesman Problem (TSP) can be described as a salesman traveling from his home
city, visiting each of the other (n - 1) cities exactly once and returning back to the home city such that
the total distance (or the total cost which is typically a function of geographical distance) travelled (
expensed) is minimized.
TSP traces its origin to the so-called Icosian Game, invented in the 1880.s by the Irish
mathematician Sir William R. Hamilton. The goal is to find a way to visit all 20 points of a two
dimensional representation of an icosahedrons, without visiting any point more than once.
Figure 7: A solution to Hamilton.s Icosian Game
What makes Traveling Salesman Problem so interesting is the fact that it is NP-Complete (solvable
in non-deterministic polynomial-time). This means that for n nodes, the time T it takes for a non-
Page 35
deterministic (brute force exhaustive search) method to solve the problem grows faster than any power
of n. This in effect means that it has to be solved by some heuristic. Examples of NP-complete
problems include the Hamiltonian cycle and the Traveling Salesman Problem (See chapter 4 for a
detailed description of NP problems)
According to Applegate et al. (2002) the largest solved instance of the Traveling Salesman Problem
is a tour of 15,112 cities in Germany. The computation was carried out on a network of 110 processors
located at Rice and Princeton Universities. The total computer time used in the computation was 22.6
years, scaled to a Compaq EV6 Alpha processor running at 500 MHz. The optimal tour has a length of
approximately 66,000 kilometers.
The Traveling Salesman Problem can be applied to many industrial applications, such as
microprocessor manufacturing, transportation and logistics problems, etc.
3. Vehicle routing problems (VRP):
Vehicle Routing Problem (VRP) is one of the most important topics in operations research. It deals
with determining least cost routes from a depot to a set of scattered customers. The routes have to
satisfy the following set of constraints:
• Each customer is visited exactly once
• All routes start and end at the depot
• Sum of all demands on a route must not exceed the capacity of a vehicle
Figure 8: An example solution to a Vehicle Routing Problem
Depot
Page 36
VRP is closely related to TSP, and according to Bullheimer et al. (1997), as soon as the customers
of the VRP are assigned to vehicles, the problem is reduced to several TSPs. based on the following
two criteria:
• Whether the vehicle is capacitated or incapacitated (is there a limit on how many
passengers or objects a vehicle can take at any given time)
• Whether it has one or more starting points (does the vehicle pick passengers or objects from
a central location (i.e. a bus terminal, or a warehouse), or a pick-up can occur on a number of
places)
Gendreau and Potvin (1998) devised a schematic to classify VRP variants:
many-to-many one-to-many
Capacitated dial-a-ride feeder system
Uncapacitated express mail delivery courier or repair services
Table 1: Vehicle Routing Problem classification
Many-to-many problems are the ones where each customer‘s request needs both a pickup and a
delivery location versus One-to-many (many-to-one) where each request include a single pickup
(delivery) location. Many-to-many problems with capacity constraints are typically the most difficult
ones because pick-up and delivery locations must be located on the same line, and the pick-up point
must always precede the delivery location.
Dial-a-ride Problem (DARP), also known as the Stacker Crane Problem, comes in two flavors
depending on whether the vehicle is allowed to leave objects on intermediate locations and later pick
them up and deliver them. DARP arises in several practical applications (Charikar M., Raghavachari
B) such as transportation of elderly or disabled persons, tele-buses and shared taxi services.
The Courier Services application (Gendreau and Potvin (1998)) refers to the local part of
international shipping services (e.g. federal express) where the load should be collected from different
location and brought back to the depot for further processing. This is to be contrasted with a local
express mail delivery service both pickup and delivery are in the same area and are serviced by the
same vehicle.
In the following section we briefly discuss several different variants of VRP.
Page 37
4. Different types of VRP:
There are several different variants of the VRP.
Capacitated Vehicle Routing Problem (CVRP) : This is the homogeneous VRP.
Single/Multiple Depot VRP (SDVRP/MDVRP): The customers get their deliveries from
single or several depots.
VRP with Time Windows (VRPTW): In this case, a time window (starttime, endtime,
servicetime) is associated to each customer.
VRP with Pick-Ups and Deliveries (VRPPD): If the vehicle picks something up and delivers
it to the customer.
Stochastic VRP (SVRP): If any component has a random behavior.
Periodic VRP (PVRP): If the delivery is in some days.
Split Delivery VRP (SDVRP): Several vehicles serve a customer.
VRP with Backhauls (VRPB): When the vehicle must pick something up from the customer
AFTER ALL deliveries are done.
These are the basic problems but we may find complex problems containing two or more of these
problems together, i.e. we may have multiple depots VRP with time windows.
We explain them in following sections.
4.1. Capacitated Vehicle Routing Problem (CVRP)
CVRP is a Vehicle Routing Problem (VRP) in which a fixed fleet of delivery vehicles of
uniform capacity must service known customer demands for a single commodity from a common
depot at minimum transit cost. That is, CVRP is like VRP with the additional constraint that every
vehicle must have uniform capacity of a single commodity.
I. Formal definition of CVRP:
Let G = (V, E) be a complete graph with vertex set V= {0, . . . ,n} and edge set E.
Vertices 1, . . . , n correspond to the customers;
Vertex 0 corresponds to the depot;
Page 38
A nonnegative cost cij is associated with each edge (i, j) E representing the travel cost
between vertices i and j (cost structure is assumed to be symmetric, i.e. cij = cji and cii =
0).
Each customer i {1, . . . , n} is associated with a known demand di ≥ 0 to be delivered
(the depot has a fictitious demand d0 = 0).
A set of K identical vehicles, each with capacity C, is available at the depot (we assume
that di ≤ C for all i {1, . . . , n}).
II. The objective of CVRP
Find a collection of K simple circuits in the graph G (each circuit corresponding to a
vehicle route) with a minimum cost such that:
Each customer is served by a single vehicle route,
Each vehicle route leaves from and returns to the depot,
Sum of the demands of the customers visited by each vehicle route does not exceed given
vehicle capacity C.
4.2. Single/Multiple depot Vehicle Routing Problem
In the Single depot Vehicle Routing Problem (SDVRP), multiple vehicles leave from the
single location and return to the same location after finishing their assigned duty. The Multi depot
vehicle routing problem (MDVRP) is a generalization of SDVRP in which multiple vehicles have
to leave from multiple depots and return to their original depot.
As we know VRP consist of two problems: Routing problem (which customers are served
by which vehicles or routes) and Scheduling problem (which customer is served first, second and
so on in each route). In MDVRP because there are additional depots for storing the products, the
decision makers also have to determine which customers are served by which depots, that is, the
grouping problem prior to the routing and scheduling problems. Obviously, this type of problem
is more challenging and sophisticated than the single-depot VRPs. The MDVRP like other VRP
problems is also NP-Hard, so exact methods are not available.
Page 39
4.3. Vehicle Routing Problem with Time Windows
Vehicle Routing Problem with Time Windows is one of the well known problems in
contemporary operation research. The objective is to find an optimal route to deliver packages to
customers in the specific time they have identified to receive their packages, considering vehicle
and package size and possibly some additional constraints.
A formal definition of VRPTW can be stated as: let G=(V, A) be a graph with node set V=
VN ∪ {v0} and arc set A, where VN = {vi ∈ V│ i =1,2,…n} stand for customer nodes and v0
stands for the central depot, where all routes start and end. Each node vi ∈ V has an associated
demand qi , service time si , service time window [ ei ,li ] and an ordered pair of coordinates (xi
,yi). Based on the geographical coordinates, it is possible to calculate the distance d ij between
every two distinct nodes vi and vj , and the corresponding travel time tij .
Under the time window constraints there may or may not be a transition (an arc) between
certain node pairs. The set of arcs can be defined as A= {(vi ,vj) │vi ,vj ∈ V ∧ toi + si + tij ≤ lj}.
If the vehicle reaches the customer vi before the ei , a waiting time occurs. The route‘s schedule
time is the sum of the travel time, waiting time and the service time.
The objective of VRPTW is to service all customers while minimizing the number of
vehicles, travel distance, schedule time and waiting time without violating vehicles‘ capacity
constraints and the customers‘ time windows.
Some of the most useful applications of the VRPTW include bank deliveries, postal
deliveries, industrial refuse collection, national franchise restaurant services, school bus routing,
security patrol services and JIT (just in time) manufacturing.
I. Different types of VRPTW:
Some of the important mixed VRP problems including time windows are as follow:
Pickup Delivery Problem with Time Windows (PDPTW)
In the PDPTW (Nanry and Barnes, 2000; Li and Lim, 2003), each transportation
request specifies a single origin and a single destination, instead of just transporting
between depot and peripheral locations.
The VRP with backhauls and time windows (Thangiah, Potvin, and Sun, 1996; Duhamel,
Potvin, and Rousseau, 1997) is a special case of PDPTW where the deliveries precede
Page 40
pickups. In Angelelli and Mansini (2001), pick-ups and deliveries at customers are
performed simultaneously.
Inventory routing problem with time windows, where inventory management at customer
sites is combined with route planning.
The fleet size and mix vehicle routing problem with time windows (Liu and Shen, 1999;
Dullaert et al., 2002) combines tactical selection of the heterogeneous vehicle fleet with
routing.
VRPTW with multiple depots which is considered by Cordeau et al. (2001)
Periodic VRPTW. Lund, Madsen, and Rygaard (1996), Shieh and May (1998)
Dynamic VRPTW, where a subset of customers and demands are unknown beforehand.
Studied by Gendreau et al. (1999)
…..
4.4. Vehicle routing problem with pickups and deliveries
There exists an extensive literature on routing problems with pickups and deliveries, some
consider ‗‗many-to-many‘‘ problems involving deliveries between customer locations like the
ones that have been reviewed in Cordeau et al.(in press) and some other review ‗‗one-to-many‘‘
and ‗‗many-to-one‘‘ features in which all customer deliveries originate at a unique depot, and all
collections are destined to the depot.
Most published VRPPD models (see, e.g., Angelelli and Mansini, 2001; Nagy and Salhi,
2005) assume that each customer is visited only once but some heuristics (Gribkovskaia et al.,
2001; Hoff and Løkketangen, in press; Nagy and Salhi, 2005) allow two visits to the same
customer. As suggested by Halskau and Gribkovskaia (2002), it is preferable to design models
and heuristics capable of constructing general solutions in the sense that some customers may be
visited once while others may be visited twice, and no a priori shape is imposed on the solution.
Page 41
Problems in this field may vary according to the needs of customers. We will discuss some
of them in following sections.
4.4.1. Vehicle routing problem with simultaneous pick-up and delivery
The vehicle routing problem with simultaneous pick-up and delivery (VRPSPD) is a basic
problem in reverse logistic which may define as follow: a set of vehicles with limited capacity
must visit a set of customers in a network, each customer need to receive given amount of
goods, pickup of given amount of waste or both. All vehicles have to go back to the depot
where they have started their travel. All goods are collected from the depot for delivering and
all waste must be carried to the depot. The objective is to minimize the overall length of the
vehicle routes.
I. Problem formulation:
A VRPSDC instance is defined by the following data:
a set of N customers to be visited, numbered 1,…, N;
a depot, numbered 0;
a directed graph G(N+;A), with vertex set N+ = N{0} including the customers
and the depot and with a complete arc set A;
weight function c : A Z+ satisfying the triangular inequality (i.e. cij ≤ cik +
ckj for all i, j, k N+);
an integer non-negative collection demand pi and an integer non-negative
delivery demand di associated with each customer i N;
a maximum number K of available vehicles;
a capacity Q of each vehicle.
The mixed-integer programming model of the VRPSPD according to Mauro et al.
(2006) includes three variables for each arc: a binary variable xij takes value 1 if and only if
arc (i, j) A belongs to the solution; continuous non-negative variables Pij and Dij indicate
respectively the amount of collected load and delivery load carried along arc (i, j).
Page 42
V RPSPD)
𝑚𝑖𝑛 𝑐𝑖𝑗 𝑖,𝑗 ∈𝐴
𝑥𝑖𝑗 1
𝑠. 𝑡. 𝑥𝑖𝑗𝑗∈𝑁+
= 1 ∀𝑖 ∈ 𝑁 2
𝑥0𝑗
𝑗 ∈𝑁
≤ 𝐾 3
𝑥𝑖𝑗𝑗 ∈𝑁+
= 𝑥𝑗𝑖𝑗 ∈𝑁+
∀𝑖 ∈ 𝑁+ 4
𝑃𝑖𝑗𝑗∈𝑁+
− 𝑃𝑗𝑖𝑗∈𝑁+
= 𝑝𝑖 ∀𝑖 ∈ 𝑁 5
𝐷𝑗𝑖𝑗∈𝑁+
− 𝐷𝑖𝑗𝑗∈𝑁+
= 𝑑𝑖 ∀𝑖 ∈ 𝑁 6
𝑃𝑖𝑗 + 𝐷𝑖𝑗 ≤ 𝑄𝑥𝑖𝑗 ∀ 𝑖, 𝑗 ∈ 𝐴 7
𝑃𝑖𝑗 ,𝐷𝑖𝑗 ≥ 0 ∀ 𝑖, 𝑗 ∈ 𝐴 8
𝑥𝑖𝑗 ∈ 0,1 ∀ 𝑖, 𝑗 ∈ 𝐴 (9)
Constraints (2) force every customer to be visited once; constraint (3) implies that no
more than K vehicles can be used; constraints (4), (5) and (6) are flow conservation
constraints on the number of vehicles and on the amounts of pick-up and delivery load;
constraints (7) ensure that the vehicle capacity is not exceeded.
The VRPSPD arises naturally in the planning of reverse logistics operations involving the
delivery of full bottles and the collection of empty ones (Dethloff, 2001; Tang and Galva˜o,
2002, 2006). Real-life applications encountered in the beverage industry are described by
Halskau and Løkketangen (1998) and Prive´ et al. (in press). Min (1989) has investigated an
application related to the public library distribution system, while Mosheiov (1994) provides
yet another application arising in the transportation of children in a community program.
Applications encountered in mail transportation are described by Wasner and Za¨phel (2004).
Page 43
Most known algorithms for the VRPSPD and the VRPPD have been developed in contexts
where the solution has a predefined shape. All are heuristics that include a construction phase
followed by an improvement phase which moves customers between different routes or
operates on a single route at a time. Typical movements include customer relocations in
different positions, 2-opt and 3-opt moves (Min, 1989; Halse, 1992; Mosheiov,1994; Salhi
and Nagy, 1999; Gendreau et al., 1999; Dethloff, 2001, 2002; Tang and Galva˜o, 2002, 2006;
Nagy and Salhi, 2005). Nagy and Salhi (2005) also consider the possibility of splitting
customer visits into two, or of merging the two visits during the solution process, but this
flexibility is not allowed by their problem formulation.
Tabu search has been applied by Gendreau et al. (1999), and Hoff and Løkketangen (in
press). Although there are new construction and improving heuristics including tabu search
yielding general solutions to the VRPSPD.
4.4.2. Pickup and delivery VRP problem with time windows
A useful extension of VRPTW is to handle pickup and delivery where goods must be
collected at a predetermined customer location before it is delivered to another specified
customer location. Therefore a request consists of picking up goods at one location and
delivering them to another location. Two time windows have to be considered, one for
specifying when goods can be collected (Pickup time window) and the other one which tell us
when the goods can be dropped off (Delivery time window). In addition service times for each
pickup and delivery should be considered. The service times indicate how long it will take for
the pickup or delivery to be performed. A vehicle is allowed to arrive at a location before the
start of the time window of the location, but the vehicle must then wait until the start of the
time window before initiating the operation. A vehicle may never arrive at a location after the
end of the time window of the location.
As it is not possible to consider all factors of real life problems, each may choose different
form of modeling eliminating those factors with the least importance.
Page 44
4.5. Dynamic or Stochastic vehicle routing problem
The Vehicle Routing Problem (VRP) has been studied with much interest within the last
three to four decades. The majority of these works focus on the static and deterministic cases of
vehicle routing in which all information is known at the time of the planning of the routes. In
most real-life applications though, stochastic and/or dynamic information occurs parallel to the
routes being carried out. Real-life examples of stochastic and/or dynamic routing problems
include the distribution of oil to private house-holds, the pick-up of courier mail/packages and the
dispatching of busses for the transportation of elderly and handicapped people. In these examples
the customer profiles (i.e. the time to begin service, the geographic location, the actual demand
etc.) may not be known at the time of the planning or even when service has begun for the
advance request customers.
Two distinct features make the planning of high quality routes in this environment much
more difficult than in its deterministic counterpart; firstly, the constant change, secondly, the time
horizon. A growing number of companies offer to service the customers within a few hours from
the time the request is received. Naturally, such customer service oriented policies increase the
dynamism of the system and therefore its complexity.
During the past decade the number of published papers dealing with dynamic
transportation models has been growing. The dynamic vehicle routing problem is only a subset of
these models. Psaraftis (1995) examines the main issues in this area and provides a survey of the
results found for various dynamic vehicle routing problems. Psaraftis mentions that only very few
general results for some simple versions of the dynamic vehicle routing problem have been
obtained. This fact may indicate that it is extremely difficult to obtain other general results for
more advanced problems.
In order to make clear what we mean by static routing problems and dynamic routing
problems we verbally define them as follow:
I. The Static Vehicle Routing Problem
In Static Vehicle Routing Problem:
All information relevant to the planning of the routes is assumed to be known by
the planner before the routing process begins.
Page 45
Information relevant to the routing does not change after the routes have been
constructed.
The information which is assumed to be relevant includes all attributes of the customers
such as the geographical location of the customers, the on-site service time and the demand of
each customer. Furthermore, system information as for example the travel times of the vehicle
between the customers must be known by the planner.
II. The Dynamic Vehicle Routing Problem
In Dynamic Vehicle Routing:
Not all information relevant to the planning of the routes is known by the planner
when the routing process begins.
Information can change after the initial routes have been constructed.
Obviously, the DVRP is a richer problem compared to the conventional static VRP. If the
problem class of VRP is denoted P(VRP) and the problem class of DVRP is denoted P(DVRP),
then P(VRP) ⊂P(DVRP).
The dynamic vehicle routing problem calls for online algorithms that work in real-time
since the immediate requests should be served, if possible. As conventional static vehicle routing
problems are NP − hard, it is not always possible to find optimal solutions to problems of realistic
sizes in a reasonable amount of computation time. This implies that the dynamic vehicle routing
problem also belongs to the class of NP − hard problems, since a static VRP should be solved
each time a new immediate request is received.
Psaraftis (1980) refers to the solution xt of the current problem pt as a tentative solution.
The tentative solution corresponds to the current set of inputs and only those. If no new requests
for service are received during the execution of this solution, the tentative route is said to be
optimal.
In Figure 9 a simple example of a dynamic vehicle routing situation is shown. In the
example, two un-capacitated vehicles must service both advance and immediate request
Page 46
customers without time windows. The advance request customers are represented by black nodes,
while those that are immediate requests are depicted by white nodes. The solid lines represent the
two routes the dispatcher has planned prior to the vehicles leaving the depot. The two thick arcs
indicate the vehicle positions at the time the dynamic requests are received. Ideally, the new
customers should be inserted into the already planned routes without the order of the non-visited
customers being changed and with minimal delay. This is the case depicted on the right hand side
route. However, in practice, the insertion of new customers will usually be a much more
complicated task and will imply a re-planning of the non-visited part of the route system. This is
illustrated by the left hand side route where servicing the new customer creates a large detour.
Immediate request customer (Dynamic) Planned route
Advance request customer (static) New route segment
Current position of vehicle
Figure 9: A dynamic vehicle routing scenario with 8 advances and 2 immediate request customers
Generally, the more restricted and complex the routing problem is, the more complicated
the insertion of new dynamic customers will be. For instance, the insertion of new customers in a
time window constrained routing problem will usually be much more difficult than in a non-time
constrained problem. Note that in an online routing system customers may even be denied
service, if it is not possible to find a feasible spot to insert them. Often this policy of rejecting
customers includes an offer to serve the customers the following day of operation. However, in
some systems – as for instance the pick-up of long-distance courier mail - the service provider
(distributor) will have to forward the customer to a competitor when they are not able to serve
them.
Page 47
We mention some examples of the dynamic routing problems:
4.5.1. Vehicle Routing Problem with Stochastic Demands
The Vehicle Routing Problem with Stochastic Demands (VRPSD) is defined on a complete
graph G = (V,A,D), where V = {0, 1, ..., n} is a set of nodes (customers) with node 0 denoting
the depot, A = {(i, j) : i, j V, i ≠ j} is the set of arcs joining the nodes, and D = {dij : i, j
V, i ≠ j} are the travel costs (distances) between nodes. The cost matrix D is symmetric and
satisfies the triangular inequality. One vehicle with capacity Q has to deliver goods to the
customers according to their demands, minimizing the total expected distance traveled, and
given that the following assumptions are made. Customers‘ demands are stochastic variables
εi, i = 1, ..., n independently distributed with known distributions. The actual demand of each
customer is only known when the vehicle arrives at the customer location. It is also assumed
that εi does not exceed the vehicle‘s capacity Q, and follows a discrete probability distribution
pik = Prob(εi = k), k = 0, 1, 2, ...,K ≤Q. A feasible solution to the VRPSD is a permutation of
the customers s = (s(1), s(2), . . . , s(n)) starting at the depot (that is, s(1) = 0), and it is called a
priori tour. The vehicle visits the customers in the order given by the a priori tour, and it has to
choose, according to the actual customer‘s demand, whether to proceed to the next customer
or to go to depot for restocking. Sometimes the choice of restocking is the best one, even if
the vehicle is not empty, or if its capacity is bigger than the expected demand of the next
scheduled customer, this action is called ‗preventive restocking‘. The goal of preventive
restocking is to avoid the bad situation when the vehicle has not enough loads to serve a
customer and thus it has to perform a back-and-forth trip to the depot for completing the
delivery at the customer. In the VRPSD, the objective is to find a priori tour that minimizes
the expected distance traveled by the vehicle, which is computed as follows. Let s = (0, 1, . . .
, n) be a priori tour. After the service completion at customer j, suppose the vehicle has a
remaining load q, and let fj(q) denote the total expected cost from node j onward. With this
notation, the expected cost of the priori tour is f0(Q). If Lj represents the set of all possible
loads that a vehicle can have after service completion at customer j, then, fj(q) for q Lj
satisfies fj(q)=Minimum{fpj(q),frj(q)},where
Page 48
𝑓𝑗𝑝 𝑞 = 𝑑𝑗 ,𝑗+1 + 𝑓𝑗+1 𝑞 − 𝐾 𝑝𝑗+1,𝐾 + [2𝑑𝑗+1 ,0
𝐾:𝐾>𝑞𝐾:𝐾≤𝑞
+ 𝑓𝑗+1(𝑞 + 𝑄 − 𝐾)]𝑝𝑗+1 ,𝐾 , (1)
𝑓𝑗𝑟 𝑞 = 𝑑𝑗 ,0 + 𝑑0,𝑗+1 + 𝑓𝑗+1
𝐾
𝐾−1
𝑄 − 𝐾 𝑝𝑗+1 ,𝐾 (2)
With the boundary condition fn(q) = dn,0 , q Ln. In (1 and 2), fpj (q) is the expected cost
corresponding to the choice of proceeding directly to the next customer, while frj (q) is the
expected cost in case preventive restocking is chosen. As shown in different articles, the
optimal choice is of threshold type: given the priori tour, for each customer j there is a load
threshold hj such that, if the residual load after serving j is greater than or equal to hj, then it is
better to proceed to the next planned customer, otherwise it is better to go back to the depot
for preventive restocking.
4.6. Periodic Vehicle Routing Problem
In the periodic vehicle routing problem (PVRP), a set of customers have to be attended one
or several times, on a given time horizon. The set of dates in which a vehicle serves a customer is
not fixed a priori, but instead, a list of possible sets of dates (visiting schedules) is associated with
each customer. A fleet of vehicles is available and each vehicle leaves the depot, serves a set of
customers and, when its work shift or its capacity is over, returns to the depot. The objective of
the problem is the minimization of the total length of the routes travelled by the vehicles on the
time horizon. Solving the problem requires assigning a visiting schedule to each customer and for
each day of the time horizon, defining the routes of the vehicles in such a way that all customers,
whose assigned schedule includes that day, are served. This model is a periodic version of the
classical vehicle routing problem and this periodic characteristic is essential in various
applications like waste collection.
There exist different models in order to solve the problems in this field for example there
are articles about PVRP with intermediate facilities in which vehicles can renew their capacity at
possibly different intermediate facilities and return to depot only when the work shift is over.
Page 49
4.7. Split Delivery Vehicle Routing Problem
In the standard version of the vehicle routing problem (VRP), a homogeneous fleet of
vehicles is based at a single depot. Each vehicle has a fixed capacity and must leave from and
return to the depot. Each customer has a known demand and is serviced by exactly one visit of a
single vehicle. A sequence of deliveries (known as a route) must be generated for each vehicle so
that all customers are serviced and the total distance traveled by the fleet is minimized. Recent
algorithmic developments and computational results for heuristics that solve the VRP are covered
by Cordeau et al. 2005.
In the split delivery vehicle routing problem (SDVRP), a fleet of homogeneous vehicles
has to serve a set of customers. Each customer can be visited more than once, contrary to what is
usually assumed in the classical vehicle routing problem (VRP), and the demand of each customer
can be greater than the capacity of the vehicles. By allowing split deliveries, the potential exists to
use fewer vehicles and to reduce the total distance traveled by the fleet. However using fewer
vehicles does not necessarily reduce the total distance. No constraint on the number of available
vehicles is considered. There is a single depot for the vehicles and each vehicle has to start and
end its tour at the depot. The objective is to find a set of vehicle routes that serves all the
customers such that the sum of the quantities delivered in each tour does not exceed the capacity
of the vehicles and the total distance travelled is minimized.
The SDVRP is NP-hard (Dror and Trudeau 1990) and is difficult to solve optimally. Figure
10 shows an example from Archetti et al. 2006 which illustrates the savings in distance and
number of vehicles that can be achieved by using split deliveries.
Page 50
Figure 10: Example showing split delivery
2
41
3
0
2 2
2 2
2
2
1
1
12
a) Node 0 is the depot. Customers 1,2,3 and 4 have a demand of 3 units.Vehicle capacity is 4 units. Distance between i and j is adjacent to the edge.
1
2 3
4
0
b)VRP optimal solution with four vehicles and a total distance of 16.
4
3
32
2
1
02
1 2 2 2
2
2
1
1(3)
(1)
(2) (2)
(1)
(3)
c)SDVRP optimal solution with three vehicles and a total distance of 15.
Page 51
4.8. Vehicle Routing Problem with Backhauls
The Vehicle Routing Problem with Backhauls (VRPB), also known as the linehaul-
backhaul problem, is an extension of the VRP involving both delivery and pickup points.
Linehaul (delivery) points are sites that are to receive a quantity of goods from the single depot.
Backhaul (pickup) points are sites that send a quantity of goods back to the depot. The critical
assumption is that all deliveries must be made on each route before any pickups can be made.
This arises from the fact that the vehicles are rear-loaded, and rearrangement of the loads on the
trucks at the delivery points is not deemed economical or feasible. The quantities to be delivered
and picked up are fixed and known in advance. The vehicle fleet is assumed to be homogeneous,
each having a capacity of some weight or volume. Hence, a feasible solution to the problem
consists of a set of routes where all deliveries for each route are completed before any pickups are
made and the vehicle capacity is not violated by either the linehaul or backhaul points assigned to
the route. The objective is to find such a set of routes that minimizes the total distance traveled.
Page 52
Chapter 6 : Solution techniques for VRP
Here there is a preliminary list of techniques used for VRP:
Exact Approach
(up to 100 nodes) Branch and bound (Fisher 1994)
Heuristics
Tour construction heuristic
Tour improvement heuristic
Clark and Wright heuristic
MetaHeuristics
Tabu search
Simulated annealing
Ant Colony System
Genetic Algorithm
Hybrid methods
We briefly discuss some of these methods in next sections.
1. Branch &Bound
Branch and bound is a systematic method for solving optimization problems. B&B is a rather
general optimization technique that applies where the greedy method and dynamic programming fail.
However, it is much slower. Indeed, it often leads to exponential time complexities in the worst case.
On the other hand, if applied carefully, it can lead to algorithms that run reasonably fast on average.
For the optimal solution, the general idea of B&B is Breadth First Search (BFS) that is one of the
node selection policy in which the live nodes expands in the same order in which they were created.
But not all nodes get expanded (i.e., their children generated). Rather, a carefully selected criterion
determines which node to expand and when, and another criterion tells the algorithm when an optimal
solution has been found.
The first idea of B&B is to develop "a predictor" which we assume to lead to optimal solution in
a solution tree. This predictor is quantitative. For example in the case of minimization problem, one
Page 53
candidate predictor of any node is the cost so far. That is, each node corresponds to (partial) solution
(from the root to that node). The cost-so-far predictor is the cost of the partial solution.
With such a predictor, the B&B works as follows:
Which node to expand next: B&B chooses the live node (a node that has been generated
but whose children have not yet been generated.) with the best predictor value
B&B simply expands that node (i.e., generate all its children)
The predictor value of each newly generated node is computed, the just expanded node (E-
node) is now designated as a dead node (a generated node that is not to be expanded or
explored any further. All children of a dead node have already been expanded.), and the
newly generated nodes are designated as live nodes.
Termination criterion: When the best node chosen for expansion turn out to be a final leaf
(i.e., at level n), that when the algorithm terminates, and that node corresponds to the
optimal solution. R
Many fundamental problems can be solved with a branch and bound algorithm, such as Integer
Linear Programming, Boolean Satisfiability, and Combinatorial Optimization problems. The traveling
salesman problem is a famous example of a problem which can be solved by a branch and bound
algorithm.
2. Heuristics
Heuristics for TSP and VRP typically fall into two groups, tour construction heuristics which create
tours from scratch and tour improvement heuristics which use simple local search heuristics to
improve existing tours.
2.1. Tour construction heuristics
The implemented tour construction heuristics are the nearest neighbor algorithm and the
insertion algorithms.
I. Nearest neighbor algorithm
The nearest neighbor algorithm (Rosenkrantz, Stearns, and Philip M. Lewis, 1977) follows
a very simple greedy procedure: The algorithm starts with a tour containing a randomly
Page 54
chosen node and then always adds to the last node in the tour the nearest not yet visited node.
The algorithm stops when all nodes are on the tour.
An extension to this algorithm is to repeat it with each node as the starting point and then
return the best tour found. This heuristic is called repetitive nearest neighbor.
II. Insertion algorithms
All insertion algorithms (Rosenkrantz et al., 1977) start with a tour consisting of an
arbitrary node and then choose in each step a node k not yet on the tour. This node is inserted
into the existing tour between two consecutive nodes i and j, such that the insertion cost (i.e.,
the increase in the tour's length) d(i, k) + d(k, j) - d(i, j) is minimized. The algorithms stop
when all nodes are on the tour.
The insertion algorithms differ in the way the node to be inserted next is chosen. The
following variations are implemented:
Nearest insertion: The node k is chosen in each step as the node which is nearest to
a node on the tour.
Farthest insertion: The node k is chosen in each step as the node which is farthest
from any of the nodes on the tour.
Cheapest insertion: The node k is chosen in each step such that the cost of
inserting the new node is minimal.
Figure 11: The nearest neighbor heuristic (Bentley 1992)
Page 55
Arbitrary insertion: The node k is chosen randomly from all nodes not yet on the
tour
2.2. Tour improvement heuristics
Tour improvement heuristics are simple local search heuristics which try to improve an
initial tour. A comprehensive treatment of the topic can be found in the book chapter by Rego and
Glover (2002).
I. k-Opt heuristics
The idea is to define a neighborhood structure on the set of all admissible tours. Typically,
a tour t0 is a neighbor of another tour t if t0 can be obtained from t by deleting k edges and
replacing them by a set of different feasible edges (a k-Opt move). In such a structure, the tour
can iteratively be improved by always moving from one tour to its best neighbor till no further
improvement is possible. The resulting tour represents a local optimum which is called k-
optimal.
Typically, 2-Opt (Croes, 1958) and 3-Opt (Lin, 1965) heuristics are used in practice.
II. Lin-Kernighan heuristic
This heuristic (Lin and Kernighan, 1973) does not use a fixed value for k for its k-Opt
moves, but tries to find the best choice of k for each move. The heuristic uses the fact that
each k-Opt move can be represented as a sequence of 2-Opt moves. It builds up a sequence of
2-Opt moves, checking after each additional move whether a stopping rule is met. Then the
part of the sequence which gives the best improvement is used. This is equivalent to a choice
of one k-Opt move with variable k. Such moves are used till a local optimum is reached.
By using full backtracking, the optimal solution can always be found, but the running time
would be immense. Therefore, only limited backtracking is allowed in the procedure, which
helps to find better local optima or even the optimal solution. Further improvements to the
procedure are described by Lin and Kernighan (1973).
Page 56
2.3. Clark and Wright (1964)
An early and well-known heuristic proposed for the CVRP is the Clarke and Wright
algorithm (Clarke and Wright, 1964). This famous heuristic uses the concept of savings to rank
merging operations between routes. The savings is a measure of the cost reduction obtained by
combining two small routes into one larger route. Given two customers i and j, the associated
saving is defined as follows:
Sij = Ci0 + C0j - Cij
The algorithm starts with a solution in which each customer is served alone on a route.
Next, for all customer pairs, the saving is computed and the savings list is sorted from largest to
smallest. At each iteration of the algorithm, the next savings is considered, and if the two
associated customers which belong to two different routes can be feasibly merged into a new
route, then the routes will be merged. That is the order:
Start with an initial allocation of one vehicle to each customer (0 is the depot for
VRP)
Calculate saving Sij = Ci0 + C0j - Cij and order the saving in increasing order
At each step find the largest saving sij where:
i and j are not in the same tour
neither i and j are interior to an existing route
vehicle and time capacity are not exceeded
link i and j together to form a new tour (replacing to other routes)
Page 57
Figure 12: Examples of Clarke and Wright Saving Heuristic (Fiala 1978)
Page 58
The Clarke and Wright algorithm is very fast and relatively easy to implement, however,
given its greedy, nature the solutions obtained are often of insufficient quality with respect to
more sophisticated approaches. In particular, it should be noted that the Clarke and Wright
algorithm does not allow control over the final number of routes obtained, since the possibility of
route merging may drastically decrease after the first few iterations in tightly constrained
problems.
3. Metaheuristics
Several different definitions of metaheuristics have been suggested in the literatures. The more
common one is: ‗A metaheuristic is an iterative master process that guides and modifies the operations
of subordinate heuristics to produce efficiently high-quality solutions. It may combine intelligently
different concepts to explore the search space using adaptive learning strategies and structured
information‘ (Osman (2002)). Metaheuristics are particularly concerned with not getting trapped at a
local optimum (for problems that have multiple local optima) and/or judiciously reducing the search
space. Each metaheuristics has one or more adjustable parameters. This permits flexibility, but for any
application (to a specific class of problems) requires careful calibration on a set of numerical instances
of the problem as well as testing on an independent set of instances. Several metaheuristics are
amenable to parallel processing, that is, investigation of different solution sequences can be done in
parallel. Taillard et al (2001) present a unifying perspective on metaheuristics and Hertz and Widmer
(2003) provide some general guidelines for the design of such methods. We will discuss the most
important metaheuristics used in VRP.
3.1. Tabu search:
Tabu search is one of the most widely used metaheuristics. The method begins with a
complete, feasible solution (obtained, for example, by a constructive heuristic) and, just like local
improvement, it continues developing additional complete solutions from a sequence of
neighborhoods. However, to escape from a local optimum, moves to neighbors with inferior
solutions are permitted. Moreover, a mechanism is used that prevents cycling back to recently
visited solutions (in particular, the local optimum). Specifically, recent solutions (or attributes of
solutions) are maintained on a so-called tabu list preventing certain solutions from reoccurring for
a certain number of iterations, called the size (or length) of the list. This size is a key controllable
Page 59
parameter of the metaheuristic. A record is maintained of the best solution to date, x*, and its
objective function value f(x*). The tabu status of a move can be over-ridden through the use of a
so-called aspiration criterion. The simplest version is the following (shown for a maximization
problem): if the move leads to a solution x having f(x) > f(x*), then the move is, of course,
permitted. Typically, the procedure is terminated after either a prescribed total number of
iterations or if no improvement is achieved in some other specified number of consecutive
iterations.
There are a number of controllable parameters in a tabu search including the size of the
tabu list (and possibly how to adjust it dynamically), how to decide when it is time to diversify,
the weights to use in bringing constraints into the evaluation function etc.
3.2. Simulated annealing
Simulated annealing is another, commonly used; metaheuristic designed to permit escaping
from local optima. References include Anandalingam (2000), Dowsland (1993), and Vidal
(1993), where the latter is a monograph devoted to applications including the aforementioned
TSP, telecommunications network design, and facility location decisions. The name ‗simulated
annealing‘ is due to the fact that conceptually it is similar to a physical process, known as
annealing, where a material is heated into a liquid state then cooled back into a recrystallized solid
state. It has some similarities to tabu search. Both start with an initial complete feasible solution
and iteratively generate additional solutions, both can exactly or approximately evaluate candidate
solutions, both maintain a record of the best solution obtained so far, and both must have a
mechanism for termination (a certain total number of iterations or a prescribed number of
consecutive iterations without improvement). However, there are important differences between
these methods. First, tabu search uses adaptive memory to guide its progress, while simulated
annealing is essentially memoryless. Second, tabu search tends to permit temporarily moving to
poorer solutions only when in the vicinity of a local optimum, whereas this can happen at any
time in simulated annealing. Finally, tabu search (in its basic form) permits moving away from a
local optimum (ie diversifying) by an essentially deterministic mechanism, whereas, as we will
see, a probabilistic device is used in simulated annealing.
At any iteration k, we have a current solution xc and a candidate solution x selected (at
random or in a systematic manner) from the neighborhood N(xc). Suppose we are dealing with a
Page 60
maximization problem. As a result, if f(x)>f(xc), then x becomes the new xc on the next iteration.
If f(x)<f(xc), then there is still a chance that x replaces xc , specifically the associated probability
is:
P(xxc) = exp 𝑓 𝑥 −𝑓(𝑥𝑐 )
𝑇𝑘
Where Tk is a parameter which be called temperature. The probability of accepting the
inferior solution x is seen to decrease as the performance gap between xc and x increases or as the
temperature becomes smaller. The sequence of temperatures usually satisfies T1≥T2≥…, that is,
the temperature is gradually decreased. There are various mechanisms of achieving this, a
common one being to maintain a fixed temperature (T) for a specified number (n) of iterations,
then use φT for the next n iterations, then φ2T for the next n iterations etc, where φ is a
controllable parameter satisfying 0<φ<1. Decreasing temperatures mean that in the early
iterations diversification is more likely, whereas in the later stages the method resembles simple
local improvement. Of course, one can use a more sophisticated dynamic control of T where it
can, for example, be temporarily increased any time it appears that the procedure has stalled at a
local optimum (see Osman 1993). When the search is terminated, it makes sense to do a
subsequent local search to ensure that the final solution is at a local optimum.
As with any metaheuristic, there are a number of controllable parameters in simulated
annealing, in particular, the sequence of temperatures (eg the initial temperature and the φ value)
and the termination criteria.
3.3. Ant colony optimization
This type of metaheuristic emulates the behavior of ant colonies in developing the shortest
route between their nest and a food source. Early work was carried out by Dorigo et al(1996) (see
also Dorigo and DiCaro(1999) and Michaelwicz and Fogel (2000) ).
The ant colony optimization (ACO) algorithms were developed by observing real ant
colonies. The ants are social insects. They live in colonies and their behavior is governed by the
goal of colony survival rather than being focused on the survival of individuals. The behavior that
provided the inspiration for ACO is the ants‘ foraging behavior, and in particular, how ants can
find shortest paths between food sources and their nest. When searching for food, ants initially
explore the area surrounding their nest in a random manner. While moving, ants leave a chemical
Page 61
pheromone trail on the ground. Ants can smell pheromone. When choosing their way, they tend to
choose, in probability, paths marked by strong pheromone concentrations. As soon as an ant finds
a food source, it evaluates the quantity and the quality of the food and carries some of it back to
the nest. During the return trip, the quantity of pheromone that an ant leaves on the ground may
depend on the quantity and quality of the food. The pheromone trails will guide other ants to the
food source. It has been shown in Deneubourg et. al (1990) that the indirect communication
between the ants via pheromone trails enables them to find shortest paths between their nest and
food sources. This is explained in an idealized setting in Fig. 13.
There are many applications and several variations, but the fundamental concepts are
conveyed in the following way related to the earlier defined TSP.
Consider a specific ant at a particular city (node) i. The probability of transition to another
node j (not already visited) depends upon two factors. The first is the direct distance dij (or
inversely, the visibility) between the two nodes, the probability being proportional to the
visibility, viz.: (1/dij)α. The second factor is the remaining amount (zij) of a physical secretion, by
earlier ants that have traversed that link, with the probability being proportional to (zij)β. α and β
are two controllable parameters of the method as is the total number of ants (m). After all m ants
have chosen a tour the remaining physical secretion amounts are updated through
New zij = (1-ρ)old zij + Δ zij
Where 0<ρ<1 is another parameter that represents evaporation and Δzij is the sum of
secretions laid down on link (i, j) by all the ants. The amount laid down by ant k is
∆𝑧𝑖𝑗 𝑘 =
0 𝑖𝑓 𝑘 𝑑𝑖𝑑 𝑛𝑜𝑡 𝑢𝑠𝑒 𝑙𝑖𝑛𝑘 (𝑖. 𝑗)𝐶
𝐿𝑘 𝑜𝑡𝑒𝑟𝑤𝑖𝑠𝑒
Where C is a constant and Lk is the total length of the tour of ant k. Note that the shorter the
tour (i.e the better the solution) the more secretion occurs.
Once the updating is complete, the individual ants again select tours according to the
revised probabilities and so on.
Page 62
Figure 13: An experimental setting that demonstrates the shortest path finding capability of ant colonies.
Between the ants’ nest and the only food source, two paths of different lengths exist. In the four graphics, the pheromone trails are shown as
dashed lines whose thickness indicates the trails’ strength.
.
Page 63
3.4. Evolutionary (Genetic) algorithms (or population-based metaheuristics)
Evolutionary algorithms, as the name implies, are a class of metaheuristics that emulate
natural evolutionary processes. Sometimes the adjective ‗genetic‘ is used in lieu of ‗evolutionary‘.
A major portion of the Michaelwicz and Fogel (2000) book is devoted to the subject. Other
general references are Reeves (1993) (in which several applications are discussed), Beasley
(2002), and Goldberg (1989). Illustrative applications include production scheduling (Moon et al
(2002) and Rochat (1998)) and telecommunications systems design (Armony et al (2000)).
Evolutionary algorithms work with a group or population of solutions (in marked contrast
with earlier discussed metaheuristics). At each iteration each solution in the current population is
evaluated. The evaluations serve to select a subset of the solutions to be either used directly in the
next population or indirectly through some form of transformation or variation (adjustment of the
single solution or generation of a new solution by combining part of the solution with part of
another one). The rest of the current solutions are discarded. The parts of a solution can be
thought of as genes, adjustments of single solutions as mutations, and combination as mating to
produce offspring.
As with the earlier discussed metaheuristics, a record is maintained of the best solution to
date. Other issues are representation (how to represent a solution in the form of a vector of genes),
choosing the initial solutions, and termination. We next comment briefly on each of these as well
as providing some further detail on each of evaluation, selection, and variation.
In a problem with n 0–1 variables a natural representation is simply a vector of n 0–1
genes. In a TSP with n cities numbered 1 to n, an appropriate representation is an ordering of the
n cities (eg 5, 3, 4, 1, 2 would represent a tour going from city 5 to 3 to…to 2 to 5). Other types of
representations are discussed by Michalewicz and Fogel (2000).
The initial population can be simply randomly generated, but it makes sense to include at
least one solution that is obtained by a good (constructive) heuristic. Another possibility is to
ensure that the initial population is well distributed throughout the solution space. As with most of
the previous metaheuristics, termination results from completing a prespecified number of
iterations or through seeing a prespecified (different) number of iterations without improvement.
One might think that the evaluation of a solution, sometimes called its fitness, should
simply be based on the associated value of the objective function. However, to avoid possible
Page 64
convergence to a population of very similar solutions, it may be more appropriate to base the
subsequent selection step on a linear transformation of the objective function values or to simply
use a ranking, as opposed to absolute continuous values (Reeves (1993)).
There are a variety of possible options for the selection step. Some individuals (solutions)
can be eliminated from consideration in a deterministic manner based on their fitness levels.
Alternatively, individuals can be randomly selected (including more than once) for use in the
variation phase, where the probability of selection is based on the fitness values (or their
rankings).
Selected individuals (solutions) are subjected to forms of variation to produce individuals
for the next generation. The most common way of combining two solutions to form two new ones
is called simple cross-over. The genes of the two parents to the left of the cross-over point are
interchanged. This is illustrated in Figure 14 where the cross-over point is after the second gene.
Figure 14: An illustration of simple cross-over.
More elaborate cross-overs are possible using more than one cross-over point. Yagiura and
Ibaraki (1996), instead of cross-over, determine the common characteristics of the two parents
and then efficiently search for the best solution that satisfies these characteristics. The second
common type of variation is mutation where one or more genes of a solution are individually
changed with a small probability. There are other forms of variation, partly depending upon the
method of representation of a solution (Reeves (1993)).
Page 65
There are a considerable number of controllable parameters and other choices in the use of
an evolutionary algorithm to solve a given problem. The parameters include the size of the
population, the probability of mutation of an individual gene (which may be best varied during
the evolutionary process), the mechanism for generating the size of the mutation change when
genes are not just 0–1, the number of cross-over points etc.
There are a variety of enhancements of evolutionary algorithms. These include the handling
of constraints (Michalewicz and Fogel (2000) and Beasley (2002)) and continuous variables
(Chelouah and Siarry (2000)), approximate (rather than exact) evaluation of a solution, coping
with stochastic elements etc.
3.5. Hybrid methods
Combinations (or hybrids) of metaheuristics can be used. As an example, Osman (1993)
combines tabu search and simulated annealing. Hybrids tend to produce very good solutions but
with significantly more computational effort.
Page 66
Chapter 7 : Inventory Routing Problem
1. Introduction
The activities within SCM, as shown in Figure 15, are practically inter-related though these are
usually treated separately (Moin and Salhi, 2006). These activities have their own objectives that are
often conflicting. For instance, the marketing objectives of high customer service and maximum sales
dollars conflict with manufacturing and distribution goals. On the other hand, a good marketing
strategy will increase demand, which will also have indirect consequences on purchasing, production,
inventory and distribution. Also, inaccurate customer forecasts for products can affect a variety of
process areas, including purchasing, production, inventory and transportation. Clearly, there is a need
for these activities to be aligned, coordinated and synchronized since changes in one part of the SCM
are likely to affect the performance of other processes.
Figure 15: Related activities in SCM
One aspect of supply chain management is the distribution logistics that includes transportation
(distribution) management and inventory control. Initial research concentrated on treating these two
logistical aspects separately. However, the inventory allocation and vehicle routing decision are
interrelated in the following way. In order to determine which customers must be served and the
amount to supply each selected customer (the inventory allocation decision), the routing cost
Page 67
information is needed so that the marginal profit (revenue minus delivery cost) for each customer can
be accurately computed. On the other hand, the delivery cost for each customer depends on the vehicle
routes, which in turn requires information about customer selection and the amount of inventory
allocated for each customer. This inter-relationship between the inventory allocation and vehicle
routing has recently motivated some authors to model these two activities simultaneously. This
practical and challenging logistical problem is known as the integrated Inventory Routing Problem
(IRP). This combined problem can be seen as an extension of the Vehicle Routing Problem (VRP)
where the orders are specified by the customers and the aim of the supplier is to satisfy these
customers while minimizing its total distribution cost. Whereas in the IRP the orders are determined
by the supplier, obviously based on some input from the customers whose aim are to minimize the
sum of the inventory cost and the distribution cost. In other words, the IRP is a medium-term problem,
whereas the VRP is a short term one. In the VRP, the question is to find (i) the delivery routes,
whereas in the IRP the question does not include (i) only but also the quantity to deliver to each
customer as well as the time for delivery. The applications of IRP arise in a variety of industries. For
instance, Campbell and Savelsbergh (2004) were inspired by the international industrial gas company,
Praxair, where one of their activities was to separate air into gases such as oxygen, hydrogen, nitrogen
and argon, which are then transported to their customers. Other applications include petrochemical
industry, suppliers of supermarkets and department stores, clothing industry, home products and the
automotive industry (see respective references in Campbell and Savelsbergh (2004)). Another
application of IRP that is not as commonly referred to as others is in the marine where ships are used
instead of trucks, several products are often being shipped in separate compartments, the inventory
activities are considered at both the sources and the destinations among other factors. Marine
inventory routing differs slightly with most IRP as the transit times are usually much longer (days
instead of hours) and the sources and the destinations often involved different countries that incur
import taxes that contribute to the inventory holding costs (Ronen, 2002).
Solution techniques for the IRP can be classified into two categories namely the theoretical
approach, where the derivation of the lower bounds to the problem is sought and a more practical
approach, where heuristics are employed to obtain the near-optimal solutions. Most papers that deal
with the theoretical approach employ some strategies that allow the IRP to be decomposed into two
underlying problems, namely the inventory and the travelling salesman problem. The inventory
problem is solved to determine the replenishment quantities for each customer as well as the
Page 68
replenishment times. Most papers in this category adopt a two-stage solution approach. They either (i)
find the routes first and then solve the IRP formulation, which is a simple linear programming-based
inventory control problem, or (ii) solve the inventory control problem first (sometimes with
approximated transportation cost), aggregate (cluster) the customers with the same replenishment time
instants and then construct the routes for each cluster. As the modification of routes entails resolving a
new inventory allocation problem and vice versa, most algorithms iterate between obtaining a new set
of routes and resolving the inventory problem until a suitable stopping criterion is satisfied. Baita et al
(1998) presented a review paper for the Dynamic Routing and Inventory Problems. The dynamicity is
defined as a situation where repeated decisions have to be taken at different times within a certain
horizon, and earlier decisions influence later decisions. The problems are usually classified according
to their practical characteristics that are defined in terms of decision variables, constraints, objectives
and cost factors, and also on the proposed approach to the solution. The classification that we use is
the same as Moin and Salhi (2006) however their classification very much follows Bramel and
Simchi-Levi (1997) whereby the problems are classified as single-period models, multi-period models,
infinite time horizon and finally those that consider the stochastic demand pattern. Other relatively
older literature reviews can be found in Campbell et al (1998) and Dror et al (1985).
2. Single-period models
Federgruen and Zipkin (1984) were among the first to integrate the inventory allocation and routing
by treating a single-period, single-item problem with random demands at the retailers. The problem
undertaken has a plant with a limited amount of available inventory and for a given day; the problem
is to allocate this inventory among the customers. The objective is, therefore, to obtain vehicle routes
and replenishment quantities for the retailers so as to minimize the expected one period cost consisting
of transportation, inventory holding and shortage costs (the end of the period inventory levels and
shortages). The ordering cost is not considered in this problem since the replenishment quantities for
each customer is determined at the plant. Using some of the ideas from vehicle routing, they develop a
non-linear mixed integer programming model which is solved using a generalized Benders‘
decomposition approach that has the property that for any assignment of customers to routes, the
problem decomposes into a non-linear inventory allocation problem which determines the inventory
and shortage costs, and a TSP for each vehicle, which yields the transportation costs. Because of
inventory and shortage costs, and the limited amount of inventory available, not every customer will
Page 69
be selected to be visited every day. This is handled in the model by the use of a dummy route that
includes all customers not receiving a delivery. The idea is to construct an initial feasible solution and
iteratively improve the solution by exchanging customers between routes. Each exchange defines a
new customer to the route assignment, which in turn defines a new inventory allocation problem and
new TSPs. Federgruen et al (1986) extend the work to the case in which the product considered is
perishable. The product in the system is classified into two classes, old units which are the ones that
will perish in the present period and fresh units which are those that are at least one period away from
their due dates. The authors adopt the solution approach of Federgruen and Zipkin (1984) with a
variation that the inventory allocation subproblems account for two product classes. Both papers
present a comparison of the integrated to the sequential approach. Federgruen and Zipkin (1984) show
that about 6, 7% savings can be achieved through a combined approach. The travel costs are found to
be substantially less using a combined approach and it was noted that for most instances, the delivery
requirements can be met with one vehicle less than those of the sequential approach of Federgruen et
al (1986). Chien et al (1989) propose an integrated approach to a single-period IRP and formulate it as
a mixed integer programming problem. The problem consists of a central depot with fixed supply
capacities and many customers with deterministic demand. The entire demand need not be satisfied
but there is a penalty cost imposed per unit of unsatisfied demand. The objective is to maximize profit
that consists of total revenue minus the penalty cost and routing costs. A Lagrangian based procedure
to generate good upper bounds is also proposed. The procedure provided good quality solutions when
tested on a set of randomly generated problems. Although the model was based on a single-period
approach, it passes some information from one period to the next through the inter-period inventory
flow, and hence can be seen to simulate a multiple-period planning model which is about to be
reviewed next. Although the single-period models may not reflect the long-term planning, the models
are still of some relevance as they are sometimes used as the basis in the study of multiperiod models.
Furthermore, in most IRPs, the demand at each retailer is sometimes difficult to predict with certainty
and can only be best represented with random variables with known probability. In such situations,
long-term planning may be prone to adjustments and hence not completely viable.
3. Multi-period models
Many short-term approaches have the tendency to defer as many deliveries as possible to the next
planning period. This flexibility adds complexity to the problem, and hence the proper projection of a
Page 70
long-term objective into a short-term planning period is essential. The objective function needs to
capture the costs and benefits of delivering to the customers earlier than necessary. This is often
achieved by decomposing a multi-period problem into a series of single-period problems using the
single-period objective function as a surrogate for long-term cost.
The first effort to study the effect of the short-term on the long-term planning is due to Dror et al
(1985) and Dror and Ball (1987). They consider single-period models as subproblems and propose a
mixed integer programming model where effects of present decisions on later periods are accounted
for using penalty and incentive factors. Using the probability that a customer will run out on a specific
day in the planning period, the average cost to deliver to the customer, and the anticipated cost of
stock out, the optimal replenishment day t* minimizing the expected total cost can be determined for
each customer. If t* falls within the short-term planning period, the customer will definitely be visited,
and an expected increase in future cost if the delivery is made on day t instead of on t*, is computed
for each of the days in the planning period. If t* falls outside the short-term planning period, then a
future benefit can be computed for making a delivery on day t of the short-term planning period. These
two computed values reflect the long-term effects of short-term decisions. An integer program, that
minimizes the sum of these costs plus the transportation costs, is solved to assign customers to
vehicles and to particular days. The routing problem is then tackled at the second stage. In their model,
the inventory holding costs are not included in the objective function. Here, only customers who will
reach their safety stock level during a particular time interval are serviced and the model only
considers a fixed number of identical trucks. We note that the delivery amounts are not decision
variables as these are dictated by the day of the week on which the delivery is to be made. Dror and
Levy (1986) use a similar analysis to yield a weekly schedule, but then they apply a heuristic using
node and arc exchanges to reduce costs in the planning period. In both papers, the demand that occurs
at the retailers/customers is considered to be deterministic. The same idea has been extended and
improved in Trudeau and Dror (1992) and Dror and Trudeau (1996). In Trudeau and Dror (1992),
stochastic demands are considered while both deterministic and stochastic demands are employed in
Dror and Trudeau (1996). Both papers solved a slightly different model with a specific application to
supply and distribution of oil and gas. In these models, a single item has to be delivered from one
depot to many retailers/customers, whose demand is different in each period.
Trudeau and Dror (1992) develop heuristics, based on linear mixed integer programming
submodels to solve their problems. The objective is to develop routing patterns, so as to meet the
Page 71
demands and minimize the long-run average transportation costs. In particular, Dror and Trudeau
(1996) focus on the maximization of operational efficiency (average number of units delivered in one
hour of operation) and the minimization of the average number of stock out in one period. Jaillet et al
(1997) and Bard et al (1998) extend the idea of Dror et al (1985) but using a slightly different
approach. First, an expected total cost of restocking a customer in a given period is derived, then an
optimal frequency to restock a customer is determined by identifying the minimum point on the
corresponding cost curve. The assignment of customers to days of the week over the planning horizon
is based on the optimal value of the frequency and the incremental cost which is incurred by not
servicing a customer on his/her optimal day. If the best day to visit falls within the planning horizon,
the customer is selected and the routing of these customers then follows. We note that they used a bi-
criteria approach as a performance measure whereby the assignment of customers to days of the week
is based solely on the incremental cost while the routing of customers is determined using the
minimization of the total distance travelled. The problem they attempted consists of a central depot
and customers who need replenishing to prevent stock out due to the high costs of scheduling a special
delivery when stocks out occur. They considered the presence of satellite facilities where vehicles can
be refilled (other than the depot) and customer deliveries continued until a closing time is reached.
They take a rolling horizon approach to the problem by determining a schedule for 2 weeks. The idea
is to model 2 weeks schedule while implementing only the first week. The problem is solved again in
the following week for the next 2 weeks horizon. Campbell and Savelsbergh (2004) develop a model,
using a vendor-managed resupply policies, which considers routing customers together on a day where
none of them are at the point of running out of stock, but if combined they can make a full or near-full
truckload delivery route. Vendor-managed resupply, through the rapid development in communication
technology, is the emerging trend in management of logistic systems and it has been claimed to
provide a win–win situation for both suppliers and customers. In the vendor managed resupply, the
inventory at each customer is monitored by the suppliers and the replenishment of products to different
customers is coordinated at the suppliers‘ level. Consequently, this eliminates the ordering cost from
the objective function. The authors propose a two-phase solution approach implemented in a rolling
horizon framework. In phase I, an approximation of the problem is constructed based on a k days
planning using integer programming to find the customers to serve each day and how much to serve
them. The obtained solution is then used as information for phase II where the daily scheduling plan
takes place. The distribution plan is constructed for a month to reflect the long-term nature of the
Page 72
planning problem, but implemented only for the first few days. This is repeated as often as necessary
using the latest information available. In phase I, a large set of possible clusters are generated and the
cost of serving each cluster is estimated. In the second phase, the departure times and customer
sequence for the different vehicles are carried out using an insertion heuristic for solving the vehicle
routing with time windows. In order to balance between the long-term and short-term objectives, the
solutions from phase I is treated as suggestion but followed as closely as possible. A small deviation is
allowed whereby the deliveries are allowed to be split into small portions, if only it gives a better
solution. We note that the inventory cost is not explicitly defined in the objective function since the
problem undertaken is for a large industrial gases company.
It is argued that in a rolling horizon framework as this, the emphasis should be on the quality and
detail of the decisions concerning the first few days of the plan, since it is only on these days where the
plan is implemented. Speranza and Ukovich (1994) study a slightly different problem where several
products have to be shipped on a common link (from one origin to one destination) such that the sum
of inventory and transportation costs is minimized. The main focus of the paper is to investigate a
shipping strategy, that is, a rule stating when shipments must take place and how products must be
loaded on vehicles (with finite capacities) in a multi-period scenario. They propose a discrete
frequency approach where shipments can only take place at some given discrete times. In addition, the
different numbers of products require a slight modification to the objective function to take into
account the quantity of each product requested by a given retailer, the different demand patterns for
each product, and in some instances the different holding costs for each product. Most models, as in
Speranza and Ukovich (1994), assume the demand rate for each product to be constant. They
experimented with different shipment strategies and it was found that allowing products to be split
among several shipping frequencies makes trucks travelling at high frequencies to be filled up
completely. Speranza and Ukovich (1998) compare the results of Speranza and Ukovich (1994) for the
discrete frequency approach with the economic order quantity (EOQ)-based solution for the shipment
of several items from one origin to one destination using trucks of a given capacity. It is worth noting
that most of the earlier work reported in the literature (see for example, Federgruen and Zipkin (1984),
Federgruen et al (1986)) or the ones that may come further like Anily and Federgruen (1990), Anily
(1994)) are based on EOQ formulation. One major drawback of these models is that they produced
frequencies that can be non-integer (and some even non-rational) and hence it can be impractical to
implement in practice (Baita et al, 1998). One of the immediate solutions, suggested by Hall (1985), is
Page 73
to round-off the EOQ value to the nearest feasible frequency, but Speranza and Ukovich (1998) show
that this strategy leads to larger costs which can be well over 20% above the ideal minimum. Despite
this drawback such results can be useful as they act as lower bounds for comparison purposes. Bertazzi
et al (1997) extend the work of Speranza and Ukovich (1994) to tackle the more general case of
several destinations. They introduce the concept of split deliveries where the quantity of a product
required at a destination may be split between different shipments, possibly with different frequencies.
This allows for a better utilization of the vehicles, thus reducing the transportation cost, but the
flexibility obviously adds to the complexity of the problem. For simplicity, most multi-product models
assume that each retailer requires only one type of product, and for split deliveries, a new constraint is
also introduced to ensure that the total amount of products requested at each retailer is fulfilled. The
authors propose a set of decomposition heuristics starting from a link by link (ie direct shipping)
solution of the problem, and then performing a local search looking for improvement through
consolidation. In the second phase, customers visiting at the same frequency are considered for
aggregation on the same route. The possibility of further reducing costs by choosing different
frequency is also investigated. In the final phase, customers with the same frequency are consolidated
again, and routes are designed. Bertazzi et al (2002) study a multi-period, multi-product with
deterministic demand for order-up-to level inventory policy. The system consists of a common
supplier in which a set of products is shipped to several retailers. Each product is made available at the
supplier and absorbed by the retailers in a deterministic (the quantity is known at each discrete time
instant) and time-varying (the quantity varies from one discrete time instant to the other) way. The
order-up-to level policy ensures that, every time a retailer is visited, the quantity delivered is such that
the maximum level of inventory is reached. Since the inventory costs are imposed at both the supplier
and the retailer, the objective function has to be modified accordingly. Two additional constraints have
to be included in the formulation to ensure that no shortages occur at the supplier and the inventory
level is not lower than the prescribed level. The authors propose a two-step heuristic algorithm to solve
the problem. In the first stage, a constructive heuristic inserts customers with the same time instant
into the routes based on the minimum cost policy (costs represent the sum of the transportation cost
and the inventory costs both at the supplier and the retailer) in which the retailer that incurs the least
cost is inserted in the solution. The second part of the heuristic exchanges customers on two different
routes if this leads to an improvement in the total cost. The solution procedure is implemented only for
a single-product and a single-vehicle case. We note that the multi-product case can be handled by
Page 74
replacing each retailer by a set of retailers, one for each product absorbed by the retailer. This leads to
setting the transportation costs to zero for retailers in the same set and the transportation costs will
only be incurred for nodes from different sets.
Lee et al (2003) study the IRP in an automotive part supply chain that comprises several suppliers
and an assembly plant. The problem addressed is based on a finite horizon, multi-period, multi-
supplier and a single assembly plant partsupply network where a fleet of capacitated identical vehicles
transport parts from the suppliers to meet the demand specified by the assembly plant for each period.
This problem represents an in-bound logistic problem of type many-to-one network and is equivalent
to the one-to-many under certain conditions. The authors propose a mixed integer programming model
to minimize the overall transportation cost and the inventory carrying cost. This mixed integer
programming model is decomposed into two subproblems, namely the VRP and the inventory control.
A heuristic based on simulated annealing is proposed to generate and evaluate alternative sets of
vehicle routes while a linear program determine the optimum inventory levels for a given set of routes.
Then, a route perturbation routine is implemented to modify a set of vehicle routes based in some
information obtained from the optimal solution to the linear program. The modification of routes
entails resolving the linear program to get new inventory levels. This scheme is carried out iteratively
until a stopping criteria is reached, namely the specified maximum number of iterations. They also
observe an important property that the optimal solution is dominated by the transportation cost
regardless of the magnitude of the unit inventory carrying cost. This claim is then proven analytically
for a simpler version of the above problem based on an infinite planning horizon and stationary
demand with a single supplier providing either a single-part type or multiple-part types. A slight
variation of the IRP that involves the use of vehicles for which the purchase or lease agreements may
need to be signed months or even years before the start of actual delivery operations has been studied
by Webb and Larson (1995). The Strategic IRP (SIRP) is motivated by the long lead times between
the signing of purchase or lease agreements and the availability of vehicles for delivery operations.
The SIRP focuses on estimating the minimum size (cost) vehicle fleet required to supply inventory
from a central depot to spatially dispersed customers when only the probability distribution for the per
unit time demand at each customer is known. Since the determination is based on information
currently known about customers‘ usage rates, the minimum number of vehicles found must be able to
handle a reasonable amount of variation in these usage rates. Most IRP models deal with routing an
existing fleet of vehicles to supply customers whose actual demands for replenishment are known or
Page 75
can be estimated. It is easily seen that the SIRP should encompass all possible realizations of IRP. The
work of Webb and Larson (1995) is motivated by Larson‘s earlier work (1988) undertaken for the
New York City Department of Environmental Protection. It was observed that one of the solutions
required more visits to one of the customers than necessary. This was attributed to the fact that a single
route was used to service a cluster and the replenishment intervals were determined by the customer
requiring the most frequent visits. To overcome this, Webb and Larson (1995) propose the use of
period and phase of individual customer‘s replenishment as additional decision variables. Here, the
routing solutions are based on customer-specific period and phase of replenishment and it is developed
for a simple model of the routing problem. The fleet size estimated is determined by separating the
customers into disjoint clusters and creating a route sequence for each cluster. A route sequence is a
permanent set of repeating routes. Customers are allowed to be on more than one route in the
sequence.
The multi-period models are useful in the sense that they offer a more realistic trade-off between
the strategic and the operational nature of the IRP models. These approaches generally produce a high-
quality solution while requiring significantly a larger computing effort. In addition, they allow the
effect of the long-term cost on the current schedules to be studied. Due to the increase complexity of
the problem, most multi-product and multi-period models consider deterministic demand at the
retailers and heuristic methods to find solutions for the multi-period models.
4. Infinite horizon
The objective function in the infinite horizon models often focuses on minimizing the long run or
the mean average of all the costs involved. In most infinite horizon models, the demand rate is
assumed to be constant and deterministic, and the periodic review policies for inventory are often
adopted in recent models.
Burns et al (1985) are among the first to consider an inventory replenishment problem with vehicle
routing costs for an infinite horizon one warehouse multiple retailer system. They adopt an aggregate
approach whereby much detailed information may be neglected without the analytical models losing
their capability for devising an implementable solution. Explicit formulas are often obtained in terms
of a few measurable parameters. These types of models are often easier to solve and a qualitative
insights can easily be achieved as only the most important factors are taken into account. The authors
develop an economic order quantity (EOQ-type) formulation and an analytic method is proposed to
Page 76
minimize total replenishment costs. The model considers retailers with constant demand and all
holding cost rates are assumed to be identical. The transportation cost is proportional to the Euclidean
distance travelled. It treats the transportation cost as part of the constant that measures reorder costs,
and generally neglects the dependence of transportation costs on network characteristics and vehicle
routing.
Blumenfeld et al (1985) use a similar approach to Burns et al (1985) in solving a large-scale
application problem undertaken for the General Motors Corporation. In this problem, a large number
of different products have to be shipped from 20 000 suppliers to 160 plants. The authors analyses the
tradeoff between inventory, transportation and setup costs both in the case of direct shipping and of
shipping via intermediate terminals.
One of the commonly used approaches in the infinite horizon model is based on the fixed-partition
policies. This strategy solves the problem by performing an a priori partition of the customers into
regions, where the demand of each region is roughly equal to a truckload, and then solves the TSP
within each region. Note that finding such regions optimally is NP-hard. One of the shortcomings of
this approach is that the deliveries to different regions are, in most cases, not coordinated.
However, assigning to different regions the outlets corresponding to a single retailer and
coordinating deliveries may induce further reduction of costs. The lack of coordination of the
deliveries does not minimize the rent costs related to space and facilities needed to hold the maximum
stock in a retailer warehouse.
It is worth noting that it is naturally easier to coordinate load splitting within the fixed partition
approach, which often reduces the number of tours and the distance travelled, in addition to
maximizing the vehicles capacity. However, in most cases, it is found that usually only a few retailers
are split among different routes.
Anily and Federgruen (1990) adopted the above ideas to determine an optimal replenishment for the
case of a single product, infinite horizon problems with constant but retailer dependent demand. Here,
the demand at each retailer is assumed to be the same, and each retailer consists of a number of outlets
located at the same points, thus allowing the original retailer to be assigned to different regions which
are then obtained heuristically using the circular partition scheme. The heuristic is shown to be
asymptotically optimal when the retailers‘ locations have independent and identically distributed
distance from the depot and the number of outlets grows to infinity. A two-stage heuristic has been
proposed. The first stage involves the derivation of a lower bound, which is obtained by solving a
Page 77
problem of partitioning the set of demand points into groups. In the second stage, all the groups with
the same cardinality obtained by solving the partitioning problem are combined into larger families of
demand points. In each of these families, efficient vehicle routes are constructed using regional
partitioning heuristics. The case in which the number of regions is a priori fixed is considered in Anily
and Federgruen (1991). We note that in both papers the depot (warehouse) acts as break-bulk centre
(an outside supplier) where the inventory is only kept at the retailers. Note that in Anily and
Federgruen (1990), a constraint on the number of demand points that can be replenished together is
imposed to guarantee an asymptotic convergence of the heuristic developed.
Anily and Federgruen (1993) generalizes the above problem considering a central warehouse from
which the products are distributed. Such a warehouse pays holding costs and has a limited stock, hence
it must be replenished from time to time facing fixed plus proportional costs. Here, the VRP is
equivalent to a multi-item/multi-stage inventory control problem with joint setup costs. They
considered the same problem as Anily and Federgruen (1990) but proposed a power-of-two policies,
where the replenishment intervals are power-of-two multiples of the base planning period.
Anily (1994) takes a similar approach in solving a slightly different generalization of the problem
where holding costs are retailer-dependent. For this problem, a new heuristic, regional partitioning
scheme, which is asymptotically optimal, is introduced. Due to the different holding costs rate, the
outlets are first clustered on the base of the ratio between their distance and holding cost and then
according to their geographic location. This ensures that the retailers in a single region are in close
proximity one to the other and that they have similar holding costs rates. Consequently, it is argued
that the effect of the joint replenishment on the holding cost is negligible relative to the savings on
routing costs. Working along similar ideas, Gallego and Simchi-Levi (1990) evaluate the long-run
effectiveness of direct shipping (separate loads to each customer). They concluded that direct shipping
is at least 94% effective over all inventory routing strategies whenever minimal economic lot size is at
least 71% of truck capacity. This implies that direct shipping is not an appropriate policy when many
customers require significantly less than a truckload, making more complicated routing polices the
appropriate choice. Bramel and Simchi-Levi (1997) extended the work to solve a variant of IRP in
which customers can hold an unlimited amount of inventory. The problem was first transformed into a
capacitated concentrator location problem (CCLP) and having solved that, the problem is transformed
back into a solution to IRP. The solution to the CCLP will partition the customers into disjoint sets
which translate into a fixed partition in the IRP. These partitions are then used in a similar way to the
Page 78
regions in Anily and Federgruen (1990). Viswanathan and Mathur (1997) extend the work of Anily
and Federgruen (1993) for the multi-period, multi-product problem. They present a new heuristic that
generates a stationary nested joint replenishment policy for the problem with deterministic demands. A
policy is defined as stationary if the replenishment of each item is made at equally spaced points in
time (ie with constant replenishment intervals) while a nested policy means that if the replenishment
interval of a given item is larger than that of another item, the former is a multiple of the latter. They
have adopted a power-of-two policies and the objective is to find the optimal replenishment quantities
for the products, as well as the vehicle routes to deliver these quantities, so as to minimize the average
inventory and transportation costs over a finite-time horizon. A fast greedy heuristic, initially
developed for the uncapacitated problem, is extended to group the customers into clusters. The
replenishment interval for each item is calculated by a modified EOQ formula.
Most of the infinite horizon models are based on the fixed-partition policies, and hence are
computationally quite efficient and can solve large instances. Since they can only guarantee
asymptotic results and it may sometimes provide trivial or even poor quality solutions to problems of
modest size. In addition, coordinated deliveries are very difficult to be scheduled, thus the results
obtained are either valid only in the case of independent deliveries, or can be seen as generating an
upper bound on the true cost. Although the IRP is an infinite horizon problem, most work in this area
is based on the theoretical analysis (with the exception of Blumenfeld et al, 1985; Burns et al, 1985)
and tested on randomly generated problems.
5. Stochastic IRP
Recently, many researchers have started to investigate the stochastic version of the problem
whereby it is assumed that a probability distribution is known for customer usage. The stochastic IRP
differs from the deterministic IRP in that the future usage amounts are uncertain. However, obtaining
the probability distribution of customer usage in practice is extremely complex. Kleywegt et al (1999)
formulate the IRP as a Markov decision process and propose approximation methods to find good
solutions within reasonable computational time. The computational results are presented for the
inventory routing problem with direct deliveries. Most of the stochastic IRP models deal with the
transportation and supply of gas and oil. (See eg, Federgruen and Zipkin, 1984; Trudeau and Dror,
1992; Jaillet et al, 1997; Bard et al, 1998)
Page 79
A slightly different application for a multi-item joint replenishment problem, in a stochastic setting,
with simultaneous decisions made on inventory and transportation policies is presented in Qu et al
(1999). The model deals with an inbound material-collection problem, as in Lee et al (2003), whereby
a central warehouse replenishes its stock by dispatching vehicles to collect the goods from several
geographically dispersed suppliers. The demand for each item is assumed to be stochastic and is
independent and identically distributed in the form of a Brownian motion process. The inventory cost
consists of a joint fixed replenishment cost to be shared among all the items included in a given
replenishment, as well as an item-dependent minor cost for including any specific item in that
replenishment. Inventory holding cost at the central warehouse is incurred at a constant rate per unit
time and total backlogging is assumed with a cost proportional to the total number of unit shorts. The
transportation cost comprises of a fixed cost for each stopover, plus a variable cost proportional to the
travel distance. The objective is thus to determine procedures for inventory management and vehicle
routing so that the warehouse may satisfy demand at a minimum longrun average cost per unit time.
The mathematical model proposed can be decomposed into inventory (as a master problem) and
transportation that acts as a subproblem. The master problem is solved item by item and determines
the amount, for each item, to be replenished by which supplier and the period it will be replenished.
Then for each period, a TSP is solved. A lower bound to the problem is also constructed to assess the
effectiveness of the heuristic. It was observed that a slightly better lower bound could be achieved for
a special case when each supplier produces a unique item.
Recently, Ribeiro and Lourenco (2003) incorporate both the stochastic and deterministic demands
in their models. Two types of customers are considered. The first is the customer managed inventory
(CMI) based on customers with deterministic demands. The second type of customers falls into the
vendor-managed inventory (VMI) with stochastic demands. The aim of the study is to determine the
best routes for all customers and the quantities and the days to be delivered for the VMI customers
(since the quantities and days to deliver are known for the CMI customers) over a week (5 days)
planning horizon. It is worth noting that the inventory holding cost and the stock out cost are only
incurred on the VMI customers. The model considers a single product in a multiperiod scenario and
the demand for VMI customers is modeled as a continuous random variable. The authors proposed an
iterated local heuristic to solve the problem. The model is decomposed into two subproblems, namely
inventory and VRP. First, an initial solution is obtained by solving the inventory problem (without
considering the transportation cost), then a good feasible solution is obtained by solving the VRP.
Page 80
Subsequently, the new quantities and the days to deliver for VMI customers are determined, taking
into account the delivery cost calculated from the previous step. This process is carried out iteratively
until a satisfactory solution is obtained. The computation study was carried out on randomly generated
data and it was found that the reduction on the cost depends on the problem size, proportion of VMI
customers and the unit costs chosen for the problems. Ronen (2002) proposes a combination of
heuristic and a mixed integer linear programming model for marine inventory routing. Here, a fleet of
ships or barges transport multiple products (in separate compartments) from a set of origins to a set of
destinations. The products are produced at the origins according to a production plan and consumed at
the destinations according to a demand forecast. The author handles the stochasticity of the demand
through determining appropriate levels of safety stocks. The maximal vessel size is both determined
by the loading and unloading facilities at the origins and the destinations, respectively. The results
presented show that the heuristic solutions tend to ship products as late as possible in order to save
money and retain shipping flexibility, whereas integer solutions in the linear programming model save
shipments later on. As pointed out by Ronen, in real life, IRPs are stochastic and any distribution plan
covering more than a few days will seldom be executed completely as planned. In other words, in the
stochastic scenarios any planning system needs to be flexible enough to cater for the latest changes in
the data.
Page 81
Chapter 8 : The Airline Scheduling Problem
1. Introduction:
The airline industry has been a rich source of operations research problems, mainly due to the
combinatorial nature of the problems. According to [109] the interdependences of the several phases in
the airline scheduling problem are illustrated in figure 16.
Figure 16: Phases and interdependences of the scheduling problem
Publish Timetable
The commercial flight schedule, that is, the schedule of flights that can be ―sold‖ to
passengers.
Fleet Assignment
The allocation of aircraft type (fleets) to the schedule flights.
After these two phases the planning process runs in parallel. The crew scheduling problem is
usually solved in two phases: crew pairing and crew rostering.
Passenger view
Aircraft View
Crew View
Publish
TimetableFleet
Assignment
TailAssignment
Revenue Management
Crew PairingRoster
MaintenanceCrew Rostering
Disruption Management
Passenger Recovery, Aircraft Recovery and crew Recovery
Page 82
Crew Pairing
Consist of creating anonymous pairings, starting and ending at home base. Legal
rules are applied at this time (for example, maximum duration of each flight duty period,
minimum rest time between two flight duty periods, maximum consecutive critical periods,
etc.) as well as some company rules (for example, minimum time for the rotation of the
aircraft, maximum number of flight legs in each flight duty period, maximum number of
duration days for each pairing, etc.).
Crew Rostering
Consist of assigning the pairings and other activities (for example, stand by duties,
training, and reserves) and applying legal rules (for example, days off, vacation, and limits
on duty/block time) to individual crew members.
The crew scheduling must be completed a few weeks before the day corresponding to
the start of the schedule and the result of this phase is a personalized roster for each crew
member, usually for a one month period.
Roster Maintenance
Consists of reflecting later changes, i.e., commercial flights changes, roster availability,
etc., in the crew schedule.
Tail Assignment
Consist of assigning the actual aircrafts (tail numbers) to flights and, consequently, the
routing of aircrafts individuals. This is typically done a few days before day of operations.
Revenue Management
Corresponds to the adjustment of prices and seat availability according to the market and
is carried out during the entire period from the publication of the flight timetable to the day of
operations.
Operations Control
Page 83
Or Disruption Management as called in [109] corresponds to the monitoring of the
schedule execution, trying to solve all the problems related with crew members, aircrafts and
passengers. Every change in the schedule, for example, flight delay or cancellation, aircraft fleet
change, crew members that do not report for duty, new flights scheduled, etc., that happens in this
phase must be feasible for crew as well as for aircraft and should minimize the passenger
inconvenience.
Recovery process
In most literatures recovery process are defined in order to solve occurred problems. For
example Crew Recovery is the process of solving crew related problems, Aircraft Recovery is the
process of solving aircraft related problems and Passenger Recovery is the process of solving
passenger problems.
The important part in airline scheduling problem is the planning problem so in the following
sections we focus more on planning problems.
2. Planning Problem:
According to Claude et al. (2006) typically the planning problem involves creating lines of work
referred to as rosters for aircraft and crew. The crew rosters consist of activities that can be flying,
ground duties, training, free days, and personal activities. The crew planning process usually
decomposes into two processes. In the first process, known as pairing, the (anonymous) flying
activities are created. The flight timetable is taken as input to form sequences of flights, known as
pairings or trips. The timetable generally spans a period of 4–6 weeks or one calendar month. The
main objective in this step is to use the minimum number of resources (crew) to schedule (cover) the
complete timetable. Andersson et al. (1997) and Vance et al. (1997) provide comprehensive
discussions on the pairing problem. In the second process, known as rostering, the created pairings are
assigned, together with other kinds of activities, to actual crew, in compliance with the qualifications
and previously assigned activities, referred to as pre-assignments, of the crew. The aim is to find
feasible assignments that minimize costs and match the airline‘s notion of quality of life for the crew.
One reason for this problem decomposition is the obvious combinatorial explosion that would occur if
we were to look at the possible rosters that can be composed directly from flights instead of pairings.
Page 84
The second reason is that the rules, which need to be followed at the time of planning, themselves fall
into two broad classes:
Pairing rules, which govern flight connections, working days (duties), night-stops and duty
combinations.
Roster rules with a larger range of influence. Some examples of these rules are:
o Rules limiting the number of hours the crew is allowed to work in a specified period
of time. Some of these might be applied on a rolling basis from week to week or
month to month.
o Rules ensuring that the crew is qualified for the assigned pairing. These rules
typically depend on the aircraft, airport of the pairing and the language, visas
requirements for the crew.
A comprehensive overview of the rules in rostering is given in Kohl and Karisch (2004). The third
and particularly important reason to this two step approach is that the desired qualities in a ‗‗good
solution‘‘ to the overall problem are partly based on cost. The other desired qualities required in the
solution come from the aspect of human resource management. The pairing process considers all
tangible costs associated with the operation of a given flight schedule. In the rostering process, on the
other hand, the social quality of the rosters is also given consideration. For rostering the costs model
the weights attached to various aspects of the desired solution, both for individual rosters and for the
global solution. This ‗‗planned‘‘ solution is then published to the crew, usually a few weeks in
advance, with the knowledge that the schedule will be modified later to accommodate the changes that
occur at the time of operation. The subsequent process that takes place at the operational level is the
crew recovery process, also referred to as ‗‗roster maintenance‘‘ or ‗‗tracking‘‘. The problem at this
step is to incorporate modifications arising due to changes in flight schedules, aircraft and crew
availability, while maintaining a feasible roster solution that affects as few crews as possible. This
process starts right after publication of rosters and continues right up to the day of operations. During
this period the published plan can undergo several modifications in order to ‗‗maintain‘‘ consistent
rosters for the current month.
In this process, one has to undo part of the work done during the pairing stage, say due to a flight
cancellation or delay making the original pairing impossible for the crew. So now the problem takes
Page 85
the original form, assigning flights to crew in a consistent manner. All flights are still required to be
assigned to crew through legal pairings. In the context of day of operations, solutions must be found
within 1–5 minutes. When re-planning for the current month, solutions must be found within 15–20
minutes. Finding efficient ways of solving crew problems occurring on the day of operations has been
an active area of research. Lettovsky (1997) first proposed a Bender‘s decomposition model that
integrates all three areas of resource management—Aircraft, crew, and passenger. Computational
results were provided only for the sub-problem dealing with crew pairing recovery. Yu et al. (2003)
and Wei et al. (1997) describe a successful implementation of their ‗‗crew solver‘‘, also a pairing
recovery module. These works support a two step approach to solve the crew recovery problem.
Broken pairings are repaired and new ones are built to cover unforeseen flights. However such
pairings may not necessarily fit in existing individual crew rosters. Models that address more specific
crew member information are first discussed in Lettovsky provide first computational results.
2.1. The crew planning problem
2.1.1. The pairing problem
The pairing problem deals with the construction of itineraries consisting of flights such that
all flights of a given schedule are completely covered. A flight is completely covered when all
of its basic crew resource requirements are met with sufficiently many qualified crew
members. A basic flight requirement is modeled with a crew-need vector of the kind
[F1/F2/F3//C1/C2/C3/. . .], where // are used for separating the main categories of cockpit and
cabin, and a single / for separating the number of crew required in each of the sub-categories.
For example a crew-need vector [1/1/0//2/2/0] denotes one captain and one first officer and no
flight engineer are needed in cockpit, and 2 chief cabins and 2 pursers are needed in cabin.
The scheduled flights‘ requirements must first be analyzed and partitioned into well defined
planning sub-problems. The first analysis is of primal importance, strategic in nature, for it
directly affects the solution space (and, therefore, cost quality) for the resulting solving
models. One way to reason with crew requirements is to use a decomposition technique
known as ‗slicing‘, where the crew-need vector is broken down to a set of sub-crew-need
vectors (slices) that add up equivalently. Usually the cockpit and cabin planning problems are
solved separately because of their differences in flight and duty regulations, so each flight‘s
original crew-need vector is first sliced into the cockpit and cabin slices, [1/1/0//0/0/0] and
Page 86
[0/0/0//2/2/0]. All flights in the schedule are then grouped (duplicated when need be) in the
slice categories that add up to their original crew-need. Each flight group/slice constitutes a
sub-schedule to solve, from which pairings are constructed. Collecting optimal pairing
solutions from each sub-schedule guarantees that each flight is indeed fully covered, albeit
with different pairings arising from each sub-schedule. We note immediately the consequence
of slicing all [1/1/0//2/2/0] flights into [1/1/0//0/0/0] and [0/0/0//2/2/0]: two resulting sub-
schedules, both ‗‗easy‘‘ to solve (pure 0/1 set covering problems), and cockpit crew always
flying together, likewise for cabin. Having the crew together during their duty allows for
smoother operations. On the other hand, a different slicing strategy say
[1/0/0//0/0/0],[0/1/0//0/0/0] for cockpit and [0/0/0//1/0/0], [0/0/ 0//0/1/0] for cabin, results into
four sub-schedules to solve. But this results in a harder set covering problem as the solution
spaces drastically increases to provide maximum flexibility, which is useful when solving
inextricable instances or squeezing out maximum productivity, but no so much as to ensure
smoother operations: such pairings are usually never ‗‗operationally feasible‘‘. Slicing is a
strategic solving paradigm, for all schedules do include either inextricable instances (the
resulting set covering model is infeasible), or flights with varying crew need: some with cabin
crew-need [0/0/0//2/2/0] while others [0/0/0//2/4/0]. This always happens due to fleet mixes.
No model today captures this ‗‗slicing‘‘ decision. Best practice is to slice according to greatest
common need: all [0/0/0//2/4/0] flights are first planned together with the [0/0/0//2/2/0] flights
in that slice, and then planned in [0/0/0//0/2/0] slice to cover the extra need in one slot. Again,
this is to convey the notion of keeping crew together as much as possible throughout the
sequence of flights that compose the pairings. Feasible pairings must start and end at the same
crew base. Structurally, pairings naturally group into duties—sequence of flights within a 24
hour period, with night stops between them usually away from home base as shown in Figure
17.
Figure 17: A three duty dates "Madrid" pairing
Page 87
Pairings must satisfy a large number of government regulations and collective bargaining
agreements, which vary from airline to airline. The rules dictate connections between flights
(e.g., minimum connection time), possible duties, possible night stops (e.g., no night stop at
home base), minimum rest time, and possible combinations of duties depending on total
flight/duty time.
Let S denote the set of slices to plan for, P the set of feasible pairings across all slices, xp , p
∈ P, a binary decision variable denoting whether pairing p is used, and ni the number of times
flight i must be covered in that slice, for example for slice [0/0/0//2/2/0] ni= 1. The pairing
problem is modeled as the following integer program:
𝐼𝑃1 min 𝑐𝑝𝑝∈𝑃
𝑥𝑝
𝑠𝑢𝑏𝑗𝑒𝑐𝑡 𝑡𝑜 𝑎𝑖𝑝𝑝∈𝑃
𝑥𝑝 ≥ 𝑛𝑖 ∀𝑖 ∈ 𝐼 𝑠 , ∀𝑠 ∈ 𝑆 1
𝑏𝑗𝑝𝑝∈𝑃
𝑥𝑝 ≥ 𝑚𝑗 ∀𝑗 ∈ 𝐽 2
𝑥𝑝 ∈ {𝑜, 1} ∀𝑝 ∈ 𝑃
All tangible crew costs (per diem, hotel, etc) are modeled in cp. I(s) denotes the set of
flights to cover in slice s, and aip is a binary coefficient that is one if pairing p covers flight i
and zero otherwise. If constraint (1) had an equality sign we would have a set-partitioning
model that forbids over-covering of flights, i.e., flights with more crew than required.
A generalized set covering model allows over-covering, which translates into some
pairings including so called deadheads, flights where crew is merely being transported.
Partitioning solutions are preferred because deadheading incurs extra costs. This is modeled
by adding surplus variables to constraint (1) with over-cover cost coefficients. Constraint (2)
is a set of constraints that apply to a group of pairings altogether. These are general constraints
with coefficients bjp and mj not necessarily 0–1. An example of such a constraint is a limit on
the required workload for each airline base (a base is an important location for the airline,
from where it manages the operations. An airline can have more than one base each with its
own set of resources). In this case bjp is the workload for pairing p, 1 if it starts and ends in
Page 88
base j, 0 otherwise; mj is the maximum workload allowed for base j. Set J denotes the set of
all constraint types which limit some property of a set of pairings.
2.1.2. The rostering problem
The solution to the pairing problem gives a set of flying activities, referred to as trips in the
rostering context. Now we look at the problem of assigning these trips to the crew such that
all the trips are assigned to as many crews as required by the flights in the trip and each crew
has a roster. The process of roster construction can be represented as a hierarchical
composition of planning steps at different levels.
Fig. 19 depicts this construction for the cockpit category. Level 1 describes the core
problem at the atomic level with the flights which need to be covered. In the example in the
figure, we have flights with need for a captain and first officer. To cover these flights trips
were created in the pairing process, which is represented by level 2. In order to provide actual
crew to these pairings we go to a higher level of composition represented by roster in level 3.
Figure 18: Planning for the cockpit slice [1/1/0//0/0/0]
The roster consists first of a pairing on which the crew functions as a captain (provides
1/0/0), second a vacation day (OFF), third a personal activity (e.g., a personal training course),
and finally a second pairing where the crew functions again as a captain (provides 1/0/0).
Hence the roster provides partially for the pairings‘ total crew need of level 2, which, in turn,
provide for some of the flights‘ need they cover in level 1. The non-flying activities in level 2
Page 89
found in rostering do not cover flights in level 1. However, some such activities may still be
given a fictitious need, say when vacation days (OFF, need 0/0/N, where N is the total number
of crew) are to be optimally distributed among crew, where as others are purely personal for
some crew and hence have no need at all.
The quality of the constructed roster is measured by many criteria. For example, in North
America, Bidlines, which are sequences of pairings only, are measured on the regularity of the
working patterns. In Europe, each airline models its own notion of fairness when it comes to
distributing free days, night flying duties, and favorable trip attributes. Also the distribution of
trips to crew may need to consider the crew preferences, which are typically based on
destination, hours, and credit time (pay). The solution also needs to ensure a notion of being
impartial or ‗‗fair‘‘ to all crew. This is modeled through the ‗‗fairness‘‘ component of the cost
function, which weighs different aspects for a roster. Usually, the history for each crew is
used to obtain a set of target values that should be achieved in the published roster for the
crew. These targets are continuously revised through the planning months. This is required
because some of the aspects are monitored on a rolling basis from one planning period to the
next and some are considered annually. The (European) rostering problem then becomes to
select a set of rosters that minimizes the accumulated deviations from each crew‘s targets, and
which covers all the pairings.
Finally, special additional qualifications are needed for some pairings. These are modeled
as multi-roster constraints, so called trip or flight qualification constraints that apply to a
group of crew flying through the same trip or flight. As in the pairing process the main
categories of cockpit and cabin are planned separately.
Denote by C the set of crew. Let Rc be the set of feasible rosters for crew member c ∈ C, xcr
,a binary decision variable denoting whether roster r is chosen for crew member c, A the set of
all activities to plan for (pairings and other), K the set of categories to plan for (e.g., in
cockpit: captain, first officer, and maybe an extra position for a trainee), Q the set of pairings
or flights for which an additional qualification constraint must hold. uacr is a binary coefficient
taking value 1 if activity a is covered by roster r for crew c, nak is the number of crew needed
for activity a in category k. The optimization function minimizes the total cost of all rosters
selected in the solution where fcr denotes the cost of roster r for crew c. The costs are modeled
Page 90
using the rule language Carmen Rave which incorporates the airline specific requirements
described before.
The optimization problem which needs to be solved is given by
𝐼𝑃2 min 𝑓𝑐𝑟𝑥𝑐𝑟𝑐∈𝐶,𝑟∈𝑅𝑐
𝑠𝑢𝑏𝑗𝑒𝑐𝑡 𝑡𝑜 𝑥𝑐𝑟𝑟∈𝑅𝑐
= 1 ∀𝑐 ∈ 𝐶 (3)
𝑢𝑎𝑐𝑟 𝑥𝑐𝑟 = 𝑛𝑎𝑘𝑐∈𝐶,𝑟∈𝑅𝑐
∀𝑎 ∈ 𝐴,∀𝑘 ∈ 𝐾 4
𝑣𝑎𝑞𝑐𝑟𝑐∈𝐶,𝑟∈𝑅𝑐
𝑥𝑐𝑟 ≤ 𝑏𝑎𝑞 ∀𝑞 ∈ 𝑄,∀𝑎 ∈ 𝑞 𝐴 ⊆ 𝐴 5
𝑥𝑐𝑟 ∈ 0,1 ∀𝑟 ∈ 𝑅𝑐 , ∀𝑐 ∈ 𝐶
Constraint (3) ensures only one roster per crew is selected. Constraint (4) ensures each
planned activity is covered for each crew category. Slack columns with incurred penalty cost
for these constraints model open time. Constraint (5) models the multiroster constraints,
where Q represents the set of constraints which need to be satisfied by the complete solution;
q(A) is the set of activities which have the additional constraint q. The coefficient vaqcr is the
contribution of roster r for crew c with respect to qualification q and activity a, and baq is the
limit imposed by the constraint q on rosters covering activity a. The coefficients of these
additional constraints need not be binary. Examples of constraints of type (5) are ‗‗at most one
inexperienced crew member must fly on this (all) trip(s)‘‘, ‗‗such crew members must not fly
together‘‘, ‗‗this trainee must fly with his instructor‘‘, and ‗‗at least one crew member must
speak a certain language‘‘.
The above model is solved repeatedly by generating a set of columns or rosters. The size of
the rostering problem over the whole planning period is considerable, so the problem is
decomposed using a ‗‗sliding time-window‘‘ approach. In this approach new rosters are
generated from old ones by regenerating part of the rosters which falls within the time-
window and keeping the rest of the roster fixed. The generated set of rosters is sent to the IP
solver which optimizes the model (IP2) and returns a new solution. The time-window is then
Page 91
moved forward and the process is repeated. Typically the size of the time-window is a week
and it is moved forward by a step size of two days. The iterative process continues with the
time-window moving in order to cover the whole planning period.
Page 92
Chapter 9 : Case study of a distribution network problem
1. Introduction:
In this chapter we will focus on a practical problem of VRP models. As we have mentioned until
now all VRP problems are NP-Hard problems, so usually finding the optimum solution is hard and
time consuming. Therefore engineers are searching for ways to get faster to the optimal solution.
Mathematical formulation of the VRP problem plays important part in solution run times. Always a
better mathematical model helps to find a better optimal solution in less run times.
Our objective is to analyze three different formulations of vehicle routing problems. First we
present the classical formulation, including the Miller-Tucker subtour elimination constraints. This
approach is formulated in a totally connected network, where distances between nodes have been
substituted by minimal length paths. That network representation is a priori requirement of this
formulation.
The second formulation is the so called three-index formulation of CVRP. Now a set of binary
variables representing the use of a link by each vehicle are used. Also, a second set of binary variables
indicating if a vehicle services a city have to be used.
The last formulation is an original formulation that considers a problem similar to the minimal cost
flow problem and imposes a set of constraints to achieve an optimal solution. Afterwards we use
LINGO to solve instances of the problems.
2. Formulations
The CVRP problem considers the problem of routing at minimum cost, a uniform fleet of K
vehicles, each with capacity C, to service geographically dispersed customers, each with deterministic
unit demands that must be serviced by a single vehicle.
2.1. Classical model
Data:
G= (V,A)
V=(0,1,…n) Set of n demand nodes and a single depot, denoted as node 0
A= {(i,j), iV ,jV}
di : Demand at each node i , iV\{0}
Page 93
cij : Typically, length of edge(i,j)or generalized cost of link
k: Number of vehicles
C: Capacity of each vehicle
Variables:
xij: 1 𝑖𝑓 𝑣𝑒𝑖𝑐𝑙𝑒 𝑔𝑜𝑒𝑠 𝑓𝑟𝑜𝑚 𝑛𝑜𝑑𝑒 𝑖 𝑡𝑜 𝑛𝑜𝑑𝑒 𝑗. 𝐸𝑑𝑔𝑒 𝑖, 𝑗 𝑏𝑒𝑙𝑜𝑛𝑔 𝑡𝑜 𝑜𝑛𝑒 𝑝𝑎𝑡0 𝑜𝑡𝑒𝑟 𝑤𝑖𝑠𝑒
ui: additional continuous variable for every iV\ {0} that indicate the flow in the vehicle after
it visits customer i or cumulative demand of node i
CVRP Model 1:
min cij
j∈Vi∈V
xij (1)
s. t. xij
i∈V
= 1 ∀ j ∈ V\{0} (2)
xij
j∈V
= 1 ∀ i ∈ V\{0} (3)
xi0
i∈V
= K (4)
x0j
j∈V
= K (5)
ui − uj + Cxij ≤ C − dj i, j ∈ V{0}, i ≠ j, di + dj ≤ C (6)
di ≤ ui ≤ C i ∈ V\{0} (7)
xij ∈ 0,1 i, j ∈ V (8)
Page 94
The constraint (2) and (3) force that a single vehicle goes into and out of every node; constraint
(4) and (5) ensure that a total of K vehicles leave the depot and return to it; constraint (6) and (7)
are subtour elimination constraints imposing both the capacity and connectivity of the feasible
routes.
2.2. Three-index model
This formulation is derived from classical model by adding an index k to the integer variables
xijk in order to identify which vehicle k travel arc (i,j). In addition another binary variable ykj exist
in this formulation indicating if vehicle k services customer j or not.
Data:
G= (V,A)
V=(0,1,…n) Set of n demand nodes and a single depot, denoted as node 0
A= {(i,j), iV ,jV}
di : Demand at each node i , iV\{0}
cij : Typically, length of edge(i,j)or generalized cost of link
k: (1…K) set of vehicles
C: Capacity of each vehicle
Variables:
𝑥𝑖𝑗𝑘 : 1 𝑖𝑓 𝑣𝑒𝑖𝑐𝑙𝑒 𝑘 𝑔𝑜𝑒𝑠 𝑓𝑟𝑜𝑚 𝑛𝑜𝑑𝑒 𝑖 𝑡𝑜 𝑛𝑜𝑑𝑒 𝑗.𝐸𝑑𝑔𝑒 𝑖, 𝑗 𝑏𝑒𝑙𝑜𝑛𝑔 𝑡𝑜 𝑜𝑛𝑒 𝑝𝑎𝑡0 𝑜𝑡𝑒𝑟 𝑤𝑖𝑠𝑒
𝑦𝑘𝑗 : 1 𝑖𝑓 𝑣𝑒𝑖𝑐𝑙𝑒 𝑘 𝑠𝑒𝑟𝑣𝑖𝑐𝑒𝑠 𝑛𝑜𝑑𝑒 𝑗0 𝑜𝑡𝑒𝑟𝑤𝑖𝑠𝑒
ui: additional continuous variable for every iV\ {0} that indicate the flow in the vehicle
after it visits customer i or cumulative demand of node i
Page 95
CVRP Model 2:
min cij
j∈Vi∈V
xijk
K
k=1
(1)
s. t. ykj
K
k=1
= 1 ∀j ∈ V\{0} (2)
yk0
K
k=1
= K (3)
xijk
j∈V
= xjik
j∈V
= yik i ∈ V, k ∈ 1…K (4)
di
j∈V
yik ≤ C k ∈ 1…K; i, j ∈ V{0} , i ≠ j (5)
uik − ujk + Cxijk ≤ C − dj s. t. di + dj ≤ C ; k ∈ 1…K (6)
di ≤ uik ≤ C i ∈ V{0} , k ∈ 1…K (7)
xijk ∈ 0,1 i. j ∈ V, k ∈ 1…K (8)
yik ∈ 0,1 i ∈ V, k ∈ 1…K (9)
Constraint 2 and 3 ensure that only a single vehicle services every customer iV\{0} and that K
vehicles leave the depot. Constraint 4 forces vehicle k to arrive and leave from node i only if it
services that node. Constraint 5 indicate the capacity constraint for every vehicle k , while
constraint 6 and 7 are the subtours elimination constraints.
2.3. Original formulation
This formulation is planned to work with the real network. So it considers all the nodes
including the demands‘ nodes and non demands‘ nodes. In addition it has an additional term in
objective function that is the sum of the products send by the links which also has to be minimized.
Data:
G= (V,A)
V=(0,1,…n) Set of n nodes and a single depot, denoted as node 0
Page 96
A= {(i,j), iV ,jV}
di : Demand at each node i , iV\{0}
cij : Typically, length of edge(i,j)or generalized cost of link
k: (1…K) set of vehicles(K=di / C)
C: Capacity of each vehicle
Variables:
xij= Quantity of products send by link (i,j)
zij= Number of vehicles travelling by link (i,j), integer
CVRP Model 3:
𝑀𝑖𝑛 𝑐𝑖𝑗𝑗 ∈𝑉𝑖∈𝑉
𝑧𝑖𝑗 + 𝑥𝑖𝑗𝑗 ∈𝑉𝑖∈𝑉
(1)
𝑥𝑜𝑗𝑗∈𝑉
= 𝑑𝑗𝑗 ∈𝑉
(2)
𝑥𝑗𝑖 − 𝑥𝑖𝑗𝑗 ∈𝑉𝑗∈𝑉
= 𝑑𝑖 𝑖 ∈ 𝑉{0} (3)
𝑧𝑗𝑖𝑗 ∈𝑉
− 𝑧𝑖𝑗𝑗 ∈𝑉
= 0 𝑖 ∈ 𝑉 (4)
𝑧𝑜𝑗𝑗∈𝑉
≥ 𝐾 𝑖 ∈ 𝑉\ 0 (5)
𝑧𝑖𝑗 𝑗∈𝑉
≥ 1 𝑖 ∈ 𝑉{0},𝑑𝑖 > 0 (6)
𝑥𝑖𝑗 ≤ 𝐶𝑧𝑖𝑗 𝑖 ∈ 𝑉, 𝑗 ∈ 𝑉 (7)
Constraint (2) and (3) ensure the demand of each node and the balance of flow for each node.
Constraint (4) forces the vehicles entering each node leave the node. Constraint (5) and (6) ensure
number of vehicles necessary and constraint (7) is the capacity constraint.
Page 97
3. Description of a problem
The problem consists of 11 cities (customers) which are situated as shown in the following graph
with the distances between them: The cities that need to be serviced are shown in yellow with their
requested demands written in the second half of the circles while the depot is shown in purple and the
rest of the cities are in green.
There are four cities which need to be serviced by the vehicles and the rest of the cities do not need
deliveries. The delivery cities are 3, 6, 7, and 11 with the demands of 4, 5, 4, and 8. The vehicles‘
capacities are the same and are considered 8.
Figure 19: The main graph of the 11 cities
Page 98
3.1. Experimental results
The first two models can‘t work with the real graph but instead they work with the shorten
graph which include only the delivery cities and the depot. As we have mentioned before these
models‘ formulations are based on the minimum distance. According to the main graph, the
minimum distances are calculated and are shown in table 2.
City 1(Depot) City 3 City 6 City 7 City 11
City 1 (Depot) 0 4 5 2 3
City 3 4 0 5 6 5
City 6 5 5 0 3 8
City 7 2 6 3 0 5
City 11 3 5 8 5 0
Table 2: The minimum distances between the delivery cities
We have solved the three models in LINGO 9 and the results for each model are shown in table
3.
Classic model Three- index model Original model
Minimum routes 3 3 3
No. of vehicles 3 3 3
Continuous Variables 5 15 37
Binary variables 17 75 ___
Integer variables ___ ___ 34
Computation time 00:00:00 00:00:00 00:00:01
Iterations 0 11 5069
Constraint 26 65 64
Objective Function 28 28 28
Solver B-and-B B-and-B B-and-B
Table 3: Results for the three models in case of 11 cities including 4 demand cities and the capacity of 8 for each vehicle
Page 99
The solution routes in the first two models (CVRP1 & CVRP2) are shown in the following
graphs: (Remember that they work with the reduced graph and not the real one.). They both choose
the same routes but only three-index model chooses different directions in one route, 1-3-7-1,
instead of classic model that chooses the direction 1-7-3-1.
The solution routes in Original model (CVRP3) are: 1-2-11-2-1, 1-5-3-5-1-9-7-9-1, 1-5-6-8-7-9
1. It is clear that the model works with the real network including all cities.
Now for deciding which model is the best, it is necessary to examine the three models in
different situations though one may have better results in one situation and the other in another
situation.
In the case of 11 nodes the best model is CVRP model 1 because of its less constraints and
variables in comparing with the two other models.
11
+8
7
+4
6
+5
1
3
+4
Figure 20: The reduced graph use in the first two models and their optimal solution
Page 100
We have increased the cities to 20 cities in which 14 nodes need to be serviced. The three-index
model could not find feasible solution while the other two found feasible solution. The results for
the two models are as shown in table 4.
Classic model Original model
Minimum routes 8 8
No. of vehicles 8 8
Continuous
Variables
14 67
Binary variables 179 ______
Integer variables ____ 64
Computation time 00.00.01 00.00.23
Iterations 910 1541280
Constraint 206 121
Objective Function 89 89
Solver B-and-B B-and-B
Table 4: Results for two models in case of 20 cities including 14 demand cities and the capacity of 8 for each vehicle
We again have increased the cities to 26 cities in which 19 nodes need to be serviced. The
results were that the two first models (CVRP1 and CVRP2) could not find feasible solutions while
the original model found an optimal solution. The results are as table 5.
Original model
Minimum routes 13
No. of vehicles 13
Continuous Variables 93
Binary variables ________
Integer variables 90
Computation time 00.03.10
Iterations 2090987
Page 101
Constraint 165
Objective Function 132
Solver B-and-B
Table 5: The results of Original model for 26 cities including 19 demand cities and the capacity of 8 for each vehicle
After that we examined the three models by increasing the capacity of the vehicles. We have
increased the capacity from 8 to 12. The three-index model still could not find feasible solution
while the other two have the results as shown in table 6.
Classic model Original model
Minimum routes 9 9
No. of vehicles 9 9
Continuous Variables 20 93
Binary variables 381 ___
Integer variables ___ 90
Computation time 00.00.17 00.00.23
Iterations 92793 188737
Constraint 420 165
Objective Function 100 100
Solver B-and-B B-and-B
Table 6: The results of Original model for 26 cities including 19 demand cities and the capacity of 12 for each vehicle
Figure 21 in the next page shows the changes of computation time by different number of nodes
for the classical model and the original model.
Page 102
Figure 21: Diagrams showing the changes of computation times by different size of network
0
20
40
60
80
100
120
140
160
180
200
Co
mp
uta
tio
n T
ime
(S
eco
nd
s)
Number of cities
CVRP1-Capacity:8
CVRP3-Capacity:8
CVRP1-Capacity:12
CVRP3-Capacity:12
11 nodes 26 nodes20 nodes
Page 103
4. Conclusions
In this work we tried to have a complete review of Vehicle Routing Problem (VRP) from
introduction to solution methods. The VRP is a key part of operations for an important number of
industries such as courier services, trucking companies and the demand responsive transportation
service. Therefore it has received a lot of attention from the research community which has generated
a lot of literatures which we have intended to bring an overview of the important ones. Also we had a
brief introduction to Inventory Routing Problem and Airline Scheduling Problem as long as they are
related to VRP.
In the final chapter we brought an example of a VRP practical problem and analyzed three different
types of models for the same problem. We investigated the effect of different formulations on the
problem‘s solution. We found that although some models may perform better in one situation the
others may have better solution in other cases such as larger problem size.
It‘s obvious that one has to choose the best model depend on its situation. If the company has to
service a small number of customers it‘s better to choose CVRP1 but if it has a lot of customers with
restricted capacity of vehicles it has to use the Original model. It is concluded that the Original model
is more adaptable a different situations and can be use to find feasible solution in many cases. As long
as it has more variables and more constraints but the time it takes to find the solution is not very much
longer than the Classic model. In addition in situations it is the only one to find the feasible solution.
Page 104
References
[1] Allan Larsen (2000). The Dynamic Vehicle Routing Problem. PhD thesis. ISSN 0909-
3192
[2] Anandalingam G (2000). Simulated annealing. In: Gass SI and Harris CM (eds).
Encyclopedia of Operations Research and Management Science, 2nd edn. Kluwer Academic
Publishers, Boston, pp 748–751
[3] Angelelli, E. and R. Mansini. (2001). ―The Vehicle Routing Proble with Time Windows
and Simultaneous Pickup and Delivery.‖ In: A. Klose, M.G. Speranza, and L.N. Van Wassenhove
(eds.), Quantitative Approaches to Distribution Logistics and Supply Chain Management.
Lectures Notes in Economics and Mathematical Systems. New York: Springer-Verlag, pp. 249–
268.
[4] Anily S (1994). The general multi-retailer EOQ problem with vehicle routing costs. Eur J
Opl Res 79: 451–473.
[5] Anily S and Federgruen A (1990). One warehouse multiple retailer inventory systems with
vehicle routing costs. Mngt Sci 36: 92–114.
[6] Anily S and Federgruen A (1991). Structured partitioning problems. Opns Res 39: 130–
149.
[7] Anily S and Federgruen A (1993). Two-echelon distribution systems with vehicle routing
and central inventories. In: Dror M (ed). Special Issue on Stochastic and Dynamic Models in
Transportation. Opns Res 41: 37–47.
[8] António Castro, Eugénio Oliveira. A Multi-Agent System for intelligent monitoring of
Airline Operations. (website mentioned in the Website part)
[9] Applegate D., R. Bixby, V. Chvátal, W. Cook. (2002): Solving Traveling Salesman
Problems. http://www.math.princeton.edu/tsp/
[10] Armony M, Klincewicz JG, Luss H and Rosenwein MB (2000). Design of stacked self-
healing rings using a genetic algorithm. J Heuristics 6: 85–105.
[11] B.L. Hollis, M.A. Forbes, B.E. Douglas (2006). Vehicle routing and crew scheduling for
metropolitan mail distribution at Australia Post. European Journal of Operational Research 173,
133–150
[12] Baita F, Ukovich W, Pesenti R and Favaretto D (1998). Dynamic routing-and-inventory
problem: a review. Transport Res A 32: 585–598.
[13] Bard J, Huang L, Jaillet P and Dror M (1998). A decomposition approach to the
inventory routing problem with satellite facilities. Transport Sci 32: 189–203.
Page 105
[14] Beasley JE (2002). Population heuristics. In: Pardalas PM and Resende MGC (eds).
Handbook of Applied Optimization. Oxford University Press, New York, pp 138–156.
[15] Benita M, Beamon (1998). Supply chain design and analysis: Models and methods.
International J. Production economics 55, 281-294
[16] Bentley J.L., (1992) ―Fast algorithms for geometric traveling salesman problem,‖ ORSA
Journal on Computing, vol. 4, pp. 387–411
[17] Bertazzi L, Paletta G and Speranza MG (2002). Deterministic order-up- to level policies
in an inventory routing problem. Transport Sci 36: 119–132.
[18] Bertazzi L, Speranza MG and Ukovich W (1997). Minimization of logistic costs with
given frequencies. Transport Res B 31: 327–340.
[19] Blumenfeld DE, Burns LD, Diltz JD and Daganzo CF (1985). Analyzing trade-offs
between transportation, inventory and production costs on freight networks. Transport Res B 19:
361–380.
[20] Bowersox, D.J., &Closs,D.J.(1996). Logistical management: The integrated supply chain
process, New York, NY: McGraw-Hill.
[21] Braithwaite, A., & Hall, D. (1999). Risky business: Critical decisions in supply chain
management, Logistics consulting partners. Hertfordshire, UK: LCP Ltd.
[22] Bramel J and Simchi-Levi D (1997). The Logic of Logistics. Springer: New York.
[23] Bullnheimer B., R.F.Hartl, C. Strauss. (1997): Applying the Ant System to the Vehicle
Routing Problem. Department of Management Science, University of Vienna.
[24] Burns LD, Hall RW, Blumenfeld DE and Daganzo CF (1985). Distribution strategies that
minimize transportation inventory costs. Opns Res 33: 469–490.
[25] C. Archetti, A. Hertz, and M. Speranza, 2006. A tabu search algorithm for the split
delivery vehicle routing problem, Transport Sci 40, 64–73.
[26] C. Archetti, M. G. Speranza and A. Hertz (2006). A Tabu Search Algorithm for the Split
Delivery Vehicle Routing Problem. Transportation Science, Vol. 40, No. 1, pp. 64–73
[27] C. Rego and F. Glover. Local search and metaheuristics. In Gutin and Punnen (2002),
chapter 8, pages 309-368.
[28] Campbell AM and Savelsbergh MWP (2004). A decomposition approach for the
inventory-routing problem. Transport Sci 38: 488–502.
[29] Campbell AM, Clarke LW, Kleywegt A and Savelsberg MWP (1998). Inventory routing.
In: Crainic T and Laporte G (eds). Fleet Management and Logistics. Kluwer Academic Publisher:
Boston, MA.
Page 106
[30] Charikar M., Raghavachari B. The Finite Capacity Dial-A-Ride Problem. Stanford
University and The University of Texas, Dallas.
[31] Chelouah R and Siarry P (2000). A continuous genetic algorithm designed for the global
optimization of multimodal functions. J Heuristics 6: 191–213.
[32] Chien TW, Balakrishnan A and Wong RT (1989). An integrated inventory allocation and
vehicle routing problem. Transport Sci 23: 67–76.
[33] Chopra, S., & Meindl, P. (2001). Supply chain management: Strategy, planning and
operation, Upper Saddle River, NJ: Prentice-Hall.
[34] Christian Blum (2005). Ant colony optimization: Introduction and recent trends. Physics
of Life Reviews 2, 353–373
[35] Claude P. Medard, Nidhi Sawhney (2007), Airline crew scheduling from planning to
operations. European Journal of Operational Research 183, 1013–1027.
[36] Cooper, M. C., Lambert, D. M., & Pagh, J. D. (1997). Supply chain management: More
than a new name for logistics. The International Journal of Logistics Management, 8 (1), 1-13.
[37] Cordeau, J.-F., G. Laporte, and A. Mercier. (2001). ―A Unified Tabu Search Heuristic for
Vehicle Routing Problems with Time Windows.‖ Journal of the Operational Research Society 52,
928–936.
[38] Cordeau, J.-F., Laporte, G., Potvin, J.-Y., Savelsbergh, M.W.P., in press. Transportation
on demand. In: Barnhart, C., Laporte, G.(Eds.), Transportation, Elsevier, Amsterdam.
[39] D. J. Rosenkrantz, R. E. Stearns, and I. Philip M. Lewis.(1977) An analysis of several
heuristics for the traveling salesman problem. SIAM Journal on Computing, 6(3):563-581
[40] David Pisinger, Stefan Ropke (2007). A general heuristic for vehicle routing problems.
Computers & Operations Research 34, 2403 – 2435
[41] Deneubourg J-L, Aron S, Goss S, Pasteels J-M. The self-organizing exploratory pattern
of the Argentine ant. J Insect Behaviour 1990; 3:159– 68.
[42] Dethloff, J., 2001. Vehicle routing and reverse logistics: The vehicle routing problem
with simultaneous delivery and pick-up. Operations Research Spectrum 23, 79–96.
[43] Dethloff, J., 2002. Relation between vehicle routing problems: An insertion heuristic for
the vehicle routing problem with simultaneous delivery and pick-up applied to the vehicle routing
problem with backhauls. Journal of the Operational Research Society 53, 115–118.
[44] Dorigo M and Di Caro G (1999). The ant colony optimization metaheuristic. In: Corne D,
Dorigo M and Glover F (eds). New Ideas in Optimization. McGraw-Hill, New York, pp 11–32.
[45] Dorigo M, Maniezzo V and Colorni A (1996). The ant system: optimization by a colony
of cooperating agents. IEEE Trans Systems Man Cybernet — Part B 26: 29–41.
Page 107
[46] Dowsland KA (1993). Simulated annealing. In: Reeves CR (ed). Modern Heuristic
Techniques for Combinatorial Problems. Halsted Press, New York, Chapter 2.
[47] Dror M and Ball M (1987). Inventory/routing: reduction from an annual to a short period
problem. Naval Res Logistics Q 34: 891–905.
[48] Dror M and Levy L (1986). A vehicle routing improvement algorithm comparison of a
‗greedy‘ and a matching implementation for inventory routing. Comput Opl Res 13: 33–45.
[49] Dror M and Trudeau P (1996). Cash flow optimization in delivery scheduling. Eur J Opl
Res 88(3): 504–515.
[50] Dror M, Ball M and Golden B (1985). Computational comparisons of algorithms for the
inventory routing problem. Ann Opns Res 4: 3–23.
[51] Drucker, P. F. (1998). Management's new paradigms. Forbes, October, 152-177.
[52] Duhamel, C., J.-Y. Potvin, and J.-M. Rousseau. (1997). ―A Tabu Search Heuristic for the
Vehicle Routing Problem with Backhauls and Time Windows.‖ Transportation Science 31, 49–
59.
[53] Dullaert, W., G.K. Janssens, K. S¨orensen, and B. Vernimmen. (2002). ―New Heuristics
for the Fleet Size and Mix Vehicle Routing Problem with Time Windows.‖ Journal of the
Operational Research Society 53, 1232–1238.
[54] EA Silver (2004). An overview of heuristic solution methods. Journal of the Operational
Research Society, 55, 936–956
[55] El-Houssaine Aghezzaf , Birger Raa, Hendrik Van Landeghem (2006). Modeling
inventory routing problems in supply chains of high consumption products. European Journal of
Operational Research 169, 1048–1063
[56] Enrico Angelelli, Maria Grazia Speranza (2002). The periodic vehicle routing problem
with intermediate facilities. European Journal of Operational Research 137,233-247
[57] Erik Andersson, Efthymios Housos, Niklas Kohl, Dag Wedelin, Crew pairing
optimization, in: G. Yu (Ed.), Operations Research in the Airline Industry, Kluwer Academic
Publishers., Boston, MA, 1997, pp. 228–258.
[58] Federgruen A and Zipkin P (1984). A combined vehicle routing and inventory allocation
problem. Opns Res 32: 1019–1037.
[59] Federgruen A, Prastacos G and Zipkin P (1986). An allocation and distribution model for
perishable products. Opns Res 34: 75–82.
[60] Felix T.S. Chan (2006). Design and performance evaluation of a distribution network: a
simulation approach. Int J Adv Manuf Technol (2006) 29: 814–825
[61] Fiala F., (1978) Vehicle Routing Problems, GMD-Mitteilungen, 46, Boon
Page 108
[62] Fisher, Marshall L. (1994). Optimal solution of vehicle routing problems using minimum
k-trees. Operations Research. Vol. 42, Iss. 4; p. 626
[63] G. A. Croes. (1958) A method for solving traveling-salesman problems. Operations
Research, 6(6):791-812
[64] Gallego and Simchi-Levi D (1990). On the effectiveness of direct shipping strategy for
the one-warehouse multi-retailer R-systems. Mngt Sci 36: 240–243.
[65] Gang Yu, Michael Arguello, Gao Song, Sandra McCowan, Anna White , A new era for
crew recovery at Continental Airlines, Interfaces 33 (1) (2003) 5–22.
[66] Gendreau M., J. Potvin. (1998): Dynamic Vehicle Routing and Dispatching. NEC
Research Institute.
[67] Gendreau, M., F. Guertin, J.-Y. Potvin, and E. Taillard. (1999). ―Parallel Tabu Search for
Real-Time Vehicle Routing and Dispatching.‖ Transportation Science 33, 381–390.
[68] Gendreau, M., Laporte, G., Vigo, D., 1999. Heuristics for the traveling salesman problem
with pickup and delivery. Computers & Operations Research 23, 501–508.
[69] Goldberg DE (1989). Genetic Algorithms in Search, Optimization and Machine
Learning. Addison-Wesley: Reading, MA.
[70] Gribkovskaia, I., Halskau, Ø., Myklebost, K.N.B., 2001. Models for pick-up and
deliveries from depots with lasso solutions. In: Stefansson, G., Tilanus, B. (Eds.), Proceedings of
the 13th Annual Conference on Logistics Research NOFOMA 2001. Chalmers University of
Technology, Go¨teborg, pp. 279–293.
[71] Guo Wei, Gang Yu, Mark Song (1997), Optimization model and algorithm for crew
management during irregular operations, Journal of Combinatorial Optimization 1 (3) (1997) 80–
97.
[72] Hall RW (1985). Determining vehicle dispatch frequency when shipping frequency
differs among suppliers. Transport Res B 19: 421–431.
[73] Halse, K., 1992. Modeling and solving complex vehicle routing problems, Ph.D.
dissertation, IMSOR, Technical University of Denmark.
[74] Halskau, Ø., Gribkovskaia I., 2002. Pick-up and deliveries from depots with different
sub-graphs in the solution, presented at the IFORS Conference, Edinburgh.
[75] Halskau, Ø., Løkketangen, A., 1998. Analyse av distribusjonsopplegget ved Sylte
Mineralvannfabrikk A/S, Report M9812 Møreforskning, Molde.
[76] Harilaos N. Psaraftis. 1980. A Dynamic Programming Solution to the single Many-to-
many Immediate Request Dial-a-Ride Problem. Transportation Science, 14:130-154.
Page 109
[77] Harilaos N. Psaraftis. 1995. Dynamic vehicle routing: Status and prospects. Ann. of Oper.
Res., 61:143-164
[78] Hertz A and Widmer M (2003). Guidelines for the use of metaheuristics in combinatorial
optimization. Eur J Opl Res 151: 247–252.
[79] Hoff, A., Løkketangen, A., in press. Creating lasso-solutions for the TSPPD-problem by
tabu search, Central European Journal of Operations Research.
[80] Hokey Min and Gengui Zhou (2002). Supply chain modeling: past, present and future.
Computers & Industrial Engineering 43, 231-249
[81] Irina Gribkovskaia, Øyvind Halskau sr., Gilbert Laporte , Martin Vlcek (2007). General
solutions to the single vehicle routing problem with pickups and deliveries. European Journal of
Operational Research 180, 568–584
[82] J.-F. Cordeau, M. Gendreau, A. Hertz, G. Laporte, and J.-S. Sormany, 2005 ―New
heuristics for the vehicle routing problem,‖ Logistics systems: Design and optimization, A.
Langevin and D. Riopel (Editors), Springer, New York, 2005, pp. 270–297.
[83] Jaillet P, Huang L, Bard J and Dror M (1997). A rolling horizon framework for the
inventory routing problem. Working Paper.
[84] Johnson, G. A., & Malucci, L. (1999). Shift to supply chain reflects more strategic
approach. APICS- The Performance Advantage, October (pp. 28-31).
[85] Kleywegt AJ, Nori VS and Savelsberg MW (1999). The stochastic inventory routing
problem with direct deliveries. Technical Report TLI99-01, Georgia Institute of Technology,
Atlanta, GA, USA.
[86] Ladislav Lettovsky (October 30) (1997), Airline Operations Recovery: An optimization
approach. Ph.D. Thesis, Georgia Institute of Technology
[87] Lambert, D. M., & Cooper, M. C. (2000). Issues in supply chain management. Industrial
Marketing Management, 29, 65-83.
[88] Larson RC (1988). Transporting sludge to the 106-mile site: an inventory/routing model
for fleet sizing and logistic system design. Transport Sci 22: 186–198.
[89] Lee C-G, Bozer YA and White III CC (2003). A heuristic approach and properties of
optimal solutions to the dynamic inventory routing problem. Working Paper, University of
Toronto, Toronto, Ontario, Canada.
[90] Leonora Bianchi1, Mauro Birattari2, Marco Chiarandini3, Max Manfrin2, Monaldo
Mastrolilli1, Luis Paquete3, Olivia Rossi-Doria4, and Tommaso Schiavinotto3 (2004).
Metaheuristics for the Vehicle Routing Problem with Stochastic Demands. Cahpater of a book
―Parallel Problem Solving from Nature - PPSN VIIIB‖ ISSN 0302-9743
Page 110
[91] Li, H. and A. Lim (2003). ―A Metaheuristics for the Pickup and Delivery Problem with
Time Windows.‖ International Journal on Artificial Intelligence Tools 12, 173–186.
[92] LIHUA WU and YUYUN WANG (1998). An Introduction to Simulated Annealing
Algorithms for the Computation of Economic Equilibrium. Computational Economics 12: 151–
169
[93] Liu, F.-H. and S.-Y. Shen. (1999). ―The Fleet Size and Mix Vehicle Routing Problem
with Time Windows.‖ Journal of the Operational Research Society 50, 721–732.
[94] Lund, K., O.B.G. Madsen, and J.M. Rygaard. (1996). ―Vehicle Routing Problems with
Varying Degree of Dynamism.‖ Technical Report, The Department of Mathematical Modelling,
Technical University of Denmark
[95] M Battarra, B Golden and D Vigo (2008). Tuning a parametric Clarke–Wright heuristic
via a genetic algorithm. Journal of the Operational Research Society, 59, 1568 -1572
[96] M. Dror and P. Trudeau, 1990. Split delivery routing, Naval Res Logist 37, 383–402.
[97] MA.Bramel J and Simchi-Levi D (1997). The Logic of Logistics. Springer: New York.
[98] Marcel Mourits, Joseph J.M. Evers (1995). Distribution network design: An integrated
planning support framework. International Journal of Physical Distribution & Logistics
Management, Volume 25, Issue (5),Pages 43-57
[99] Maria Candida Mourao, Lígia Amado (2005). Heuristic method for a mixed capacitated
arc routing problem: A refuse collection application. European Journal of Operational Research
160, 139–153
[100] Martin Savelsbergh, Jin-Hwa Song (2007). Inventory routing with continuous moves.
Computers & Operations Research 34, 1744–1763
[101] Mauro Dell‘ Amico, Giovanni Righini and Matteo Salani (2006). A branch-and-price
approach to the vehicle routing problem with simultaneous distribution and collection.
Transportation Science, Vol. 40, No. 2, May 2006, pp. 235-247
[102] Michael Hahsler and Kurt Hornik. (2008) Introduction to TSP-Infrastructure for the
Traveling Salesperson Problem.
[103] Michael Hahsler, Kurt Hornik (2007). TSP -Infrastructure for the Traveling Salesperson
Problem. Journal of Statistical Software, Volume 23, Issue 2.
[104] Michalewicz Z and Fogel DB (2000). How to Solve It: Modern Heuristics. Springer-
Verlag: Berlin.
[105] Min, H., 1989. The multiple vehicle routing problem with simultaneous delivery and
pick-up points. Transportation Research A 23, 377–386.
Page 111
[106] Mirela Stojkovich, Francois Soumis, Jacques Desrosiers (1998), The operational airline
crew scheduling problem, Transportation Science 32 (3) (1998) 232–245.
[107] Moon I, Silver EA and Choi S (2002). A hybrid genetic algorithm for the economic lot
scheduling problem. Int J Production Res 40: 809–824.
[108] Mosheiov, G., 1994. The travelling salesman problem with pick-up and delivery.
European Journal of Operational Research 79, 299–310.
[109] N. Kohl, A. Larsen, J. Larsen, A. Ross, and S. Tiourline (2007). Airline disruption
management -perspectives, experiences and outlook. Journal of Air Transport Management.
Volume 13, Issue 3, Pages 149-162
[110] Nagy, G., Salhi, S., 2005. Heuristic algorithms for single and multiple depot vehicle
routing problems with pickups and deliveries. European Journal of Operational Research 162,
126–141.
[111] Nanry, W.P. and J.W. Barnes. (2000). ―Solving the Pickup and Delivery Problem with
Time Windows Using Reactive Tabu Search.‖ Transportation Research, Part B 34, 107–121.
[112] NH Moin and S Salhi (2006). Inventory routing problems: a logistical overview. Journal
of the Operational Research Society (2007) 58, 1185–1194
[113] Niklas Kohl, Stefan E. Karisch (March) (2004), Airline crew rostering: Problem types,
modeling, and optimization, Annals of Operations Research 127: 223–257.
[114] OLLI BRA¨ YSY, WOUT DULLAERT, MICHEL GENDREAU (2004). Evolutionary
Algorithms for the Vehicle Routing Problem with Time Windows. Journal of Heuristics, 10: 587–
611
[115] Osman IH (1993). Metastrategy simulated annealing and tabu search algorithms for the
vehicle routing problem. Ann Oper Res 41: 421–451.
[116] Osman IH (2002). Preface: focused issue on applied metaheuristics. Comput Indust Eng
44: 205–207.
[117] P.H. Vance, C. Barnhart, E.L. Johnson, G.L. Nemhauser (1997), Airline crew scheduling:
A new formulation and decomposition algorithm, Operations Research 45 (2) (1997) 188–200.
[118] Paolo Toth (2000). Optimization engineering techniques for the exact solution of NP-
hard combinatorial optimization problems. European Journal of Operational Research 125, 222-
238
[119] Paolo Toth, Daniele Vigo (2002). The Vehicle Routing Problem. Published by SIAM
[120] Patrick Jaillet , Jonathan F. Bard , Liu Huang , Moshe Dror (2002). Delivery Cost
Approximations for Inventory Routing Problems in a Rolling Horizon Framework.
Transportation Science, Vol. 36, No. 3, pp. 292–300
Page 112
[121] Philippe Lacomme, Christian Prins and Wahiba Ramdane-Chérif (2005). Evolutionary
algorithms for periodic arc routing problems. European Journal of Operational Research 165,
535–553
[122] Prive´, J., Renaud, J., Boctor, F.F., Laporte, G., in press. Solving a vehicle routing
problem arising in soft drink distribution, Journal of the Operational Research Society
[123] Qiu-Hong Zhao, Shou-Yang Wang, K.K. Lai (2007). A partition approach to the
inventory/routing problem. European Journal of Operational Research 177, 786–802
[124] Qu WW, Bookbinder JH and Iyogun P (1999). An integrated inventory-transportation
system with modified periodic policy for multiple products. Eur J Opl Res 115: 254–269.
[125] Quan Lu, Maged M. Dessouky (2006). A new insertion-based construction heuristic for
solving the pickup and delivery problem with time windows. European Journal of Operational
Research 175, 672–687
[126] Reeves CR (1993). Genetic algorithms. In: Reeves CR (ed) Modern Heuristic Techniques
for Combinatorial Problems. Halsted Press, New York, Chapter 4.
[127] Ribeiro R and Lourenc¸o HR (2003). Inventory-routing model, for a multi-period
problem with stochastic and deterministic demand. Working Paper, Department of Economics
and Business and GRELIET, University Pompeu Fabra, Barcelona, Spain.
[128] Rochat Y (1998). A genetic approach for solving a scheduling problem in a robotized
analytical system. J Heuristics 4: 245–261.
[129] Ronen D (2002). Marine inventory routing: shipments planning. J Opl Res Soc 53: 108–
114.
[130] S. Lin and B. Kernighan.(1973) An effective heuristic algorithm for the traveling-
salesman problem. Operations Research, 21(2):498-516
[131] S. Lin. (1965) Computer solutions of the traveling-salesman problem. Bell System
Technology Journal, 44:2245-2269
[132] S.C. Ho, D. Haugland (2004). A tabu search heuristic for the vehicle routing problem
with time windows and split deliveries. Computers & Operations Research 31, 1947–1964
[133] Salhi, S., Nagy, G., 1999. A cluster insertion heuristic for single and multiple depot
vehicle routing problems with backhauling. Journal of the Operational Research Society 50,
1034–1042.
[134] Shapiro, J. F. (2001). Modeling the supply chain, Pacific Grove, CA: Wadsworth Group. [135] Shieh, H.M. and M.D. May. (1998). On-Line Vehicle Routing with TimeWindows:
Optimization-Based Heuristics Approach for Freight Demands Requested in Real-Time.
Transportation Research Record 1617, 171–178.
Page 113
[136] Si Chen , Bruce Golden
, Edward Wasil (2007). The split delivery vehicle routing
problem: Applications, algorithms, test problems, and computational results. Networks, Volume
49 Issue 4, Pages 318 – 329
[137] Speranza MG and Ukovich W (1994). Minimizing transportation and inventory costs for
several products on a single link. Opns Res 42: 879–894.
[138] Speranza MG and Ukovich W (1998). Analysis and integration of optimization models
for logistic systems. Int J Prod Econ 35: 183–190.
[139] Stevens, G. C. (1989). Integrating the supply chain. International Journal of Physical
Distribution and Materials Management, 19, 3-8.
[140] Taillard ED, Gambardella LM, Gendreau M and Potvin JY (2001). Adaptive memory
programming: a unified view of metaheuristics. Eur J Opl Res 135: 1–16.
[141] Tang, F.A., Galva˜o, R.D., 2002. Vehicle routing problems with simultaneous pick-up
and delivery service. Opsearch 39, 19–33.
[142] Tang, F.A., Galva˜o, R.D., 2006. A tabu search algorithm for the vehicle routing problem
with simultaneous pick-up and delivery service. Computers & Operations Research 33, 595–619.
[143] Teodor Gabriel Crainic and Gilbert Laporte (1998). Fleet management and Logistics.
Published by Kluwer Academic Publishers
[144] Thangiah, S.R., J.-Y. Potvin, and T. Sun. (1996). ―Heuristic Approaches to Vehicle
Routing with Backhauls and Time Windows.‖ Computers & Operations Research 23, 1043–1057.
[145] Trudeau P and Dror M (1992). Stochastic inventory routing: route design with stockouts
and route failures. Transport Sci 26: 171–184.
[146] Vaidyanathan Jayaraman (1998). Transportation, facility location and inventory issues in
distribution network design: An investigation. International Journal of Operations & Production
Management. Volume:18, Issue:5, Pages: 471-494
[147] Vidal RVV (1993). Applied Simulated Annealing. Springer-Verlag: Berlin.
[148] Viswanathan S and Mathur K (1997). Integrating routing and inventory decisions in one
warehouse multiretailer, multiproduct distribution systems. Mngt Sci 43: 294–312.
[149] Wasner, M., Za¨phel, G., 2004. An integrated multi-depot hub-location vehicle routing
model for network planning of parcel service. Journal of Production Economics 90, 403–419.
[150] Webb IR and Larson RC (1995). Period and phase customer replenishment: a new
approach to strategic inventory/routing problem. Eur J Opl Res 85: 132–148.
[151] William Ho, George T.S. Ho, Ping Ji, Henry C.W. Lau (2008). A hybrid genetic
algorithm for the multi-depot vehicle routing problem. Engineering Applications of Artificial
Intelligence 21, 548–557
Page 114
[152] Xiaoxia Zhang and Lixin Tang (2007). Disruption Management for the Vehicle Routing
Problem with Time Windows. Book chapter. ISSN 1865-0929.
[153] Yagiura M and Ibaraki T (1996). The use of dynamic programming in genetic algorithms
for permutation problems. Eur J Opl Res 92: 387–401.
[154] Yvan Dumas, Jacques Desrosiers and Francois Soumis (1991). The pickup and delivery
problem with time windows. European Journal of Operational Research 54 (1991) 7-22
Online References:
Different types of VRP: http://lcm.csa.iisc.ernet.in/scm/supply_chain_intro.html
Complexity Problems: http://encyclopedia.thefreedictionary.com/P+%3D+NP+problem
NP-Problems: http://mathworld.wolfram.com/NP-Problem.html
NP-Problems: http://en.wikipedia.org/wiki/NP-Complete
NP-Completeness: http://www.ics.uci.edu/~eppstein/161/960312.html
NP- Hard Problems: http://www.math.ohiou.edu/~just/bioinfo05/supplements/
Branch and Bound: http://www.seas.gwu.edu/~ayoussef/cs212/branchandbound.html
Chapter 12: Integer/Discrete Programming via Branch and Bound:
http://www.sce.carleton.ca/faculty/chinneck/po.html
Introduction to TSP-Infrastructure for the Traveling Salesperson Problem:
http://cran.r-project.org/web/packages/TSP/vignettes/TSP.pdf
Vehicle Routing Problems (VRPs):
http://www.idsia.ch/~luca/abstracts/papers/corso_vrp_metanet.pdf
A Multi-Agent System for intelligent monitoring of Airline Operations:
http://repositorio.up.pt/dspace/bitstream/10216/327/2/A%20MultiAgent%20System%20for%20Intelligen
t%20Monitoring%20of%20Airline%20Operations.pdf
Designing the Distribution Network in a Supply Chain:
http://www.kellogg.northwestern.edu/faculty/chopra/htm/research/deliverynetwork.pdf
The P versus NP Problem:
http://books.google.es/books?hl=es&lr=&id=7wJIPJ80RdUC&oi=fnd&pg=PA87&dq=The+P+versus
+NP+Problem&ots=3EACvcIojH&sig=GuHLnUGsS1M93R4z0co67tp3M7s
Vehicle Routing Problem with Time Windows: http://www.vacic.org/lib/vrptw.pdf
Applications of Discrete Optimization
http://www.idsia.ch/~luca/ADOGambardella2006N.pdf
Page 115
Intro to logistics and vehicle routing problem: http://cu-ocw.eng.chula.ac.th/cu/eng/ce/advanced-
topics-in-civil-enginnering-i-optimization-models-in-transportation/lecture-notes-
1/L14%20Intro%20to%20Logistics%20and%20VRP.pdf
An Overview of Genetic Algorithms: http://ralph.cs.cf.ac.uk/papers/GAs/ga_overview1.pdf
Genetic Algorithms Overview: www.geocities.com/francorbusetti/gaweb.pdf
The VRP with backhauls: http://neo.lcc.uma.es/radi-aeb/WebVRP/data/articles/VRPB.pdf
Software:
Software for model solution: LINGO 09
