# A Survey of Recent Research on Optimization Models and Algorithms for Operations Management from the Process View

Authors: Hongying Fei; Qian Li; Dan Sun
Journal: Scientific Programming
 (2017)

---

## Abstract

Over the past decades, optimization in operations management has grown ever more popular not only in the academic literature but also in practice. However, the problems have varied a lot, and few literature reviews have provided an overview of the models and algorithms that are applied to the optimization in operations management. In this paper, we first classify crucial optimization areas of operations management from the process point of view and then analyze the current status and trends of the studies in those areas. The purpose of this study is to give an overview of optimization modelling and resolution approaches, which are applied to operations management.


---

## Body

## 1. Introduction

Operations management (OM) is generally defined as the specific field of the management, which is concerned with managing along the transformation of raw materials into goods or services. It involves how to use resources in an efficient and effective way in terms of meeting customer requirements and has become one of the most widely explored researching areas. As defined in Business Dictionary, optimization is to find an alternative with the most cost-effective or highest achievable performance under the given constraints by maximizing desired factors and minimizing undesired ones. Although optimization plays an important role in operations management, and numerous literature reviews have been published on operations management topics or on some specified optimization topics, none of them provides a general view of the models and algorithms, which are dedicated to the optimization in the field of operations management. In consequence, the purpose of this study is to conduct a survey of modelling methods and algorithms, which have been applied to the optimization in operations and services management published in recent ten years.Considering that all types of business in an enterprise, which need to be driven from different parts, are based on the process for collaborative operations, OM is normally concerned with managing the process that converts inputs (raw materials, manual labor and energy, etc.) into outputs (in forms of goods and/or services); three topics are organized in this study from the process perspective so as to enable the readers to have a clear idea about the crucial optimization issues involved in such transformation process:(i)
Optimization in input management: this aspect of operations management involves decisions on how to use resources efficiently and effectively. A review on scheduling, the most important topic involved in this stage, will be detailed.(ii)
Optimization in facilities management: concerned with the input the processes, the optimization problems concerned in this stage start with particular work that has already been planned while attempting to minimize the influence of various factors that cause unexpected breakdowns or delays so that the work processes can go forward smoothly at the utmost degree. The most crucial topic that will be detailed in this aspect is production/service rescheduling taking into account maintenance operations or unexpected breakdowns.(iii)
Optimization in output management: the optimization problems in the output stage are mainly concerned with how to deliver goods or services to customers in an optimal manner. A review on vehicle routing optimization, the most important topic in the delivery system, will be detailed in this part.It is worth mentioning that only the most important topic involved in each stage is detailed in this article because it is impossible for us to give full description. Furthermore, since various review works on certain topics of operations managements have been observed in the literature, we would benefit from such studies and complement the review work by collecting publications that have appeared in recent years, especially the articles published between the year of 2010 and 2016, which can be used as a complement of the existing review studies.The purpose of this section is not to perform an exhaustive overview of the literature but to reveal the following: (1) How the optimization models are constructed? (2) What kind of methods have been developed for solving such models efficiently and effectively? (3) What have been the novel aspects of the optimizations in OM in recent years?The rest of this paper is organized as follows: a general survey on optimization criteria will be given in Section2; review on the construction of quantitative models is given in Section 3 for the selected topics, respectively; the survey on resolution methods will be given in Section 4. This paper will end up with a global overview and some perspectives.


## 2. Optimization Criteria

A large variety of optimization criteria have been employed in the literature on OM. Gralla et al. [1] explored the optimal criteria for humanitarian aid delivery models on three aspects: efficiency, effectiveness, and equity. Efficiency criteria include operations costs or travel times. Effectiveness criteria consist of the amount of the satisfied demand and/or the speed at which the demand is satisfied. According Gralla et al. [1], equity refers to fairness in distribution of services among recipients, and thus the optimal criteria concerned with equity include the latest arrival time, the sum of arrival times, and the smallest demand satisfaction rate. Gutjahr and Nolz [2] refined the scheme of Gralla et al. [1] by partitioning the group “effectiveness” into the subgroups of response time, travel distance, coverage, reliability, and security and created seven groups of optimization criteria: (1) cost, including fixed cost for the procurement of equipment, supply-side travelling cost, facility-related cost, and the costs incurred for human resources; (2) response time, such as latest arrival time and average arrival time; (3) travel distance; (4) coverage, which measures the degree to which necessary services are provided to satisfy the demands; (5) reliability, which measures the probability of being able to steadily succeed with reference to other certain criteria, such as coverage or response time, in view of an uncertain environment; (6) security, which measures operation risks; (7) equity, normally measured by considering the worst-case value of a measure of disutility, such as the latest arrival time or smallest demand satisfaction rate as proposed by Gralla et al. [1]; (8) distress, subsumed by Gutjahr and Nolz [2] in psychological or social costs. Furthermore, it is observed that sustainable development has become widely spread in recent years and more and more researchers focus their studies on sustainable operations by taking into consideration the factors of system’s sustainability [3]. Besides, some studies are now devoted to the global environmental preservation and aim at minimizing the pollution emission [4].In order to tackle more general cases, we integrate all optimization criteria observed in the references and classify the optimization criteria into three categories:(1)
Economic criteria can contribute to the measurement of the operational cost of the system, including (a) fixed cost related to the installation of facility, employment of employees, and procurement of equipment; (b) variable cost related to the operations. For example, the amount of the equipment installed, the number of employees assigned, and the travel distance mentioned by Gutjahr and Nolz [2] can be used as economic criteria.(2)
Managerial criteria can be applied to the evaluation of the managerial competence of the organization, such as the efficiency and effectiveness of operations. For instance, the response time, amount of demand satisfied, coverage, reliability, and security can be regarded as managerial criteria. Cooperation between partners can also be considered in this part.(3)
Societal criteria can be applied to measure how the decision-makers consider the corporate social responsibility. For example, the criteria that can contribute to the measurement of equity and protection of environment can be classified into this part.It is observed in the literature that optimization criteria employed in the field of scheduling, rescheduling, and distribution are quite similar though their emphasis is different from the others. For a better understanding, we will make a general elaboration based on the categories proposed above and then analyze the distribution of those optimal criteria for the three fields, respectively:(1)
Economic criteria observed are as follows: makespan, that is, completion time of the last job (as discussed by Davendra et al. [5]; Engin and Günaydin [6]; Zhang and Chen [7]); completion, including total completion time (as discussed by Framinan et al. [8]; Li et al. [9]; Nikjo and Rezaeian [10]; Shahvari et al. [11]; Sabouni and Logendran [12]) and total weighted completion time (as discussed by Bozorgirad and Logendran [13]; Correa et al. [14]); flow time, or named production time in some publications (as discussed by Sabouni and Logendran [12]; Ying et al. [15]; Lu and Logendran [16]); setup cost, including intracell movement time [17], energy cost [18, 19], and other costs that may result in augmentation of the operation cost, such as tardiness penalty (as discussed by Le and Pang [18]).(2)
Managerial criteria observed are as follows: earliness (as discussed by Arabameri and Salmasi [20]); tardiness (as discussed by Arabameri and Salmasi [20]; Jenabi et al. [21]; Aldowaisan and Allahverdi [22]); number of tardy (late) jobs [23, 24]; other criteria that may result in low efficiency and effectiveness of management, such as schedule deviation under uncertain environment (as discussed by Sölveling et al. [25]; Xiong et al. [26]).(3)
Societal criteria observed are as follows: maximum lateness (as discussed by Wang et al. [27, 28]); maximum tardiness (as discussed by Pan et al. [29]; Xie and Li [30]); pollutant emissions, including the emission of waste [31, 32] and carbon emission (as discussed by Liu [33]; Liu et al. [34]; Zheng and Wang [35], Giret et al. [36]); other societal criteria were considered in specific domains. For example, distress is considered by Gutjahr and Nolz [2] as an optimization criteria in humanitarian aid optimization.


## 3. Quantitative Illustration

### 3.1. Scheduling

Scheduling is generally used by managers to allocate necessary resources according to a given objective and the constraints. Optimization in scheduling plays an important role in both industrial and service domains because it can help decision-makers make a production/service scheduling with minimal cost or maximal output.The traditional quantitative notation used to describe a scheduling problem is proposed by Graham et al. [37]. They describe a scheduling problem by using the notation αβγ, where α defines the shop environment in terms of the setting and machine number; β defines some processing characteristics, such as shop condition and setup information; γ is used to describe the performance measure, that is, the objective function.According to the first field (α), the scheduling problems can be classified mainly into five categories:(i)
Single machine: only one machine is available for processing jobs (Cai et al. (2012); [38, 39]).(ii)
Parallel machine: a set of machines can start to process jobs simultaneously [40–42].(iii)
Flow shop: jobs are processed by a set of machines sequentially. The processing sequence of jobs through the machines must be the same [9, 43–45].(iv)
Job shop: jobs are processed by a set of machines and each job has a dedicated processing sequence; that is, the processing route of a job is not necessary to be the same with the others (Guo and Lei (2013) [46–51]).(v)
Open shop: jobs are processed by a set of machines. Different from flow shop and job shop where certain processing sequence is predefined for a job, there is no predetermined processing sequence for the jobs in open shop [52–54].With regard to the second field (β), some factors other than the processing sequence should be also considered:(1)
Wait between two consecutive operations of a job: if the no-wait constraint occurs, two successive operations of a job must be processed without any interruption and thus no-wait models are established in different environments: flow shop [55–60], hybrid/flexible workshop [61–65], job shop ([47, 66–68]), and open shop [47, 54, 69].(2)
Setup time: in traditional scheduling problems, the processing times of jobs are assumed to be fixed and independent constant values. However, in some case, a certain setup time is necessary for some on-process product to be ready for the next stage [70–73].(3)
Batch production: batch production, as an important processing way, exists in many scheduling environments [70–72, 74].The modelling of scheduling problems can also vary a lot in terms of the objective criteria, that is, the third field (γ). In fact, both single-objective scheduling and multicriteria problems have been widely studied in recent years. The single-objective problems are related just to one optimization criterion, while several optimal criteria are combined in the objective function of the multicriteria models.On the basis of the list of optimization criteria described in Section2, we have collected publications with the combination of key word “scheduling” and different optimal criteria. It is observed that the majority of the studies optimize the operations according to economic criteria and aim at maximizing economic performance. It is reasonable because both profit organizations and nonprofit organizations arrange the operations under limited budgets. It is worth mentioning that no significant differences were observed for economic and managerial criteria, whereas the number of the articles concerning societal criteria which have been published from the year 2010 onwards is about three times as great as those published before (as shown in Figure 1).Figure 1
Distribution of publications among three general optimization criteria before and from Y2010 onwards in the field of scheduling.As shown in Figure2, the economic criteria, such as completion time, makespan, and flow time, were mostly considered in studies both before and from the year 2010 onwards. Managerial criteria, such as tardiness, lateness, and earliness, were also widely considered though much fewer studies were dedicated to societal criteria.Figure 2
Proportion of the publications among different optimization criteria collected from the field of scheduling before and from Y2010 onwards.Furthermore, the comparison between the numbers of publications before and after the year 2010 (as shown in Figure3) reveals that an explosion can be observed in publications concerning energy cost, pollutant emission, and carbon emission; even they are only a very small part of the study on scheduling at present. It indicates that more and more OM researchers take into consideration both sustainable production and environment protection.Figure 3
Comparison between the numbers of publications before Y2010 and from Y2010 onwards in the field of scheduling.Furthermore, the limitation of resources also greatly influences the constructions of models. A detailed review of constraints influencing construction of scheduling models can be found in [43, 75, 76].


### 3.2. Rescheduling

Ideally, the working or service process will follow a given schedule that is optimally established at the stage of scheduling. However, in case a disturbance or a disruption occurs, the manufacturing or service system must be rescheduled because the predetermined schedule is no more feasible. In the manufacturing system, a machine disruption is said to occur when a machine becomes unavailable for some period of time for the sake of resource shortage, machine failure, or other unexpected reasons; sometimes, job disruptions can also happen when some parameters of a specific job change. Both machines failures and job disruptions can find their counterparts in service systems. For example, in the railway scheduling system, all disruptions related to trains or infrastructure can be regarded as machine disruptions though the disturbances caused by the passengers or customers can result in the so-called job disruptions. In general, a rescheduling problem inherits all the constraints from the original scheduling problem and takes into account the constraints raised from disturbances [77–80].In manufacturing domain, most of the rescheduling problems deal with machine disruptions [81–85] or machine breakdowns [86–92], while disturbances vary a lot in service industries. For example, in the transportation domain, disruptions may be caused by the delay of transportation tools [93–97]; in hospital, the arrival of emergency patients is the major reason for rescheduling [98, 99], while disruptions can be observed in computer system because of resource request failures [100, 101].Since each rescheduling problem can find its counterpart in the field of scheduling, the quantitative notation described in Section3.1 is also applicable to describing rescheduling problems. In fact, the main differences between scheduling and rescheduling are resulting from the objectives of the decision-makers.The distribution of optimization criteria employed in the field of rescheduling is quite different from that observed in the field of scheduling. As shown in Figure4, besides the criteria most frequently used for scheduling problems, schedule deviation, robustness, and equity have been also widely considered for rescheduling problems, especially in recent years.Figure 4
Distribution of the publications among different optimization criteria before and from Y2010 onwards in the field of rescheduling.According to the distribution of publications among different optimization criteria, as shown in Figure5, it is obvious that much more managerial and societal criteria are considered in rescheduling optimization; this phenomenon is due to the fact that most of the rescheduling problems are raised from the field of service managements, such as hospital management [102, 103] and transportation management [93, 96], where the requirements of the customers must also be considered.Figure 5
Distribution of publications among three general optimization criteria in the field of rescheduling before and from Y2010 onwards.


### 3.3. VRP

Starting with the study on truck dispatching problem published by Dantzig and Ramser [104] and the more generalized model developed by Clarke and Wright [105], a set of optimization problems that aim at finding an optimal way of serving a set of customers, geographically dispersed around the central depot, using a fleet of vehicles and taking into account necessary constraints, became known as the “vehicle routing problem” and became one of the most widely studied topics in the field of operations management. In recent years, its variants have grown ever more popular in the literature (as discussed by Gendreau et al. (2005a,b); Eksioglu et al. [106]; Braekers et al. [107]), though current models vary widely as more and more researchers aim to enable their models to cope with real-life complexities and the literature on vehicle routing problems has been growing exponentially at a rate of 6% each year [106, 107] and many surveys focused on specific variants can be observed as well [108–119].In general, the classical vehicle routing problem can be defined on a graphG=(V,A), where V={0,1,…,n} represents the node set that is corresponding to the depot and customers, and A=i,j∈V is set of arcs. The depot is noted as node 0 and customers are nodes j=1,2,…,n. An arc i,j∈A indicates a possible route that links nodes i and j and is associated with the cost of travelling Cij>0 from node i to node j. The vehicle routing problem is called symmetric if Cij=Cji; otherwise, it is called asymmetric [115]. A fleet of vehicles starts from a given depot to serve customers according to some predefined constraints. In general, the studies in vehicle routing problems aim to find a collection of circuits, each corresponding to a vehicle route with minimum cost, defined as the sum of the costs of the circuits’ arcs [106].In the literature, vehicle routing problems can be structured differently according to various constraints, such as capacitated VRP [120–126], the VRP with heterogeneous fleet of vehicles [127], open VRP [128–131], VRP with time windows [132–138], VPR with both pick-up and delivery [139–144], location routing problem [145–147], period VRP [148–151], multidepot VRP [152–156], VRP with backhaul [157–159], inventory routing problem [160–163], dynamic VRP [164], or the mixture [165–169].As for the definition of objective functions, both single-objective problems and multicriteria problems were widely studied in this field. Different from the studies about scheduling and rescheduling, where objective functions vary within a limited range, an interesting trend can be observed about the utilization of optimization criteria. Besides traditional economic criteria, whose meaning is similar to their counterparts in the field of scheduling and rescheduling, some other economic criteria were observed in this field:(i)
Travelling cost: this cost is associated with transportation distance or/and travelling time. This criterion is the mostly considered in the literature [133, 138, 160, 170–173];(ii)
Vehicle cost: this fixed operational cost is related to the number of vehicles. To the best of our knowledge, although some studies set the vehicle cost as their only objective [134, 144, 150, 174–178], the majority of the studies (54.3%) regard the vehicle cost as the part of fixed cost and aim to minimize the combination of the fixed cost with some variable costs, such as travelling cost [128, 133, 136, 145, 146, 179–183], penalty cost [184], inventory cost [163, 185–187], fuel cost [188], and emission [137].(iii)
Inventory cost: When integrating inventory management with vehicle routing decisions, the objective turns into not only minimizing the travelling cost or vehicle cost but also taking into consideration the inventory cost over the planning horizon [160–163, 165, 166, 185–187, 189–194].(iv)
Penalty cost: penalty costs are normally considered when the decision-makers want to make trade-off between positive and negative effects of diversions and enable an efficient application-dependent control of diversions [164]. In general, the penalty cost is raised from the punctuality of delivery [164, 182, 183, 195], the ability of meeting the demands [187, 189, 196], the capability of vehicles [184, 197], waste of product [193], congestion charge [198], and so forth.(v)
Fuel consumption: traditional vehicle routing problems often rely on costs related to transportation distance, inventory, or the fixed cost of vehicle usage; nowadays, more and more researchers try to minimize the total fuel consumption, which is not only influenced by distance or vehicles’ velocity but also related to the characteristics of each vehicle or even to the vehicle load [198–201]. In this study, this criterion is merged to the criterion “energy cost” so as to standardize the expression.(vi)
Driver cost: this cost is related mainly to the wage of the drivers and can be regarded as one important part of the fixed part of the total cost. Similar to the vehicle cost, driver cost is also determined by the number of vehicles employed [193, 195, 200, 202].(vii)
Loading/unloading cost: the loading/unloading cost is related to number of product units instead of the transportation distance. In some articles, the loading/unloading cost is considered as a part of the total operation cost [138, 160, 199, 203].(viii)
Service cost: this cost is paid for special services such as maintenance [163], opening depots [145, 146], construction of new locations [204].(ix)
Profit: profit is the most important objective of enterprises because efficient logistic operations can contribute a lot to the profits; many vehicle routing models were constructed with an objective to maximize the total expected profit ([205–207]; Kumar et al. (2017); [143]).Besides tardiness, earliness, lateness, and robustness, which can also be observed in the field of scheduling and rescheduling, some other managerial criteria were observed:(1)
Workload imbalance: ideally, vehicles that are responsible for the delivery of products along different routes should be charged similarly so as to improve the delivery efficiency. With this purpose, some studies tried to reduce the workload imbalance minimizing the travelling cost of the longest route [208–211] or balancing the daily workload [148].(2)
Coverage, that is, number of visited customers: in some variants of VRP where the assumption of visiting each customer does not hold, the maximization of the number of total visited customers is normally considered as the most important part of the objective because more customers visited show the higher efficiency of services [180, 212].Similar to scheduling and rescheduling problems, equity and emissions are also observed in the field of VRP when the decision-makers aim to build green logistic strategies, and thus the studies concerned with the reduction of emission have emerged in recent years [178, 180, 200, 213–215].As shown in Figures6 and 7, economic criteria, such as “travelling cost,” “penalty cost,” “energy cost,” and “profit,” greatly dominate the others. It is worth mentioning that except the observation of increasing attention paid to important economic criteria such as energy cost, penalty cost, and total profit of the operations, some societal criteria, such as robustness of the delivery and the emission of vehicles, began to draw more and more attentions. According to statistics, as shown in Figure 7, the portion of publications concerning societal criteria has increased from 7% to 10% since the year 2010.Figure 6
Distribution of publications among detailed optimization criteria in the field of VRP before and from Y2010 onwards.Figure 7
Distribution of publications among three general optimization criteria before and from Y2010 onwards in the field of VRP.To sum up, not only economic criteria but also managerial criteria and societal criteria were widely considered in the literature on OM optimization, though the economic ones were mostly considered both before and after the year 2010 in all targeted topics. Furthermore, we have observed that mathematical programming is widely used to construct quantitative models of the optimization problems, in all targeted fields, that will be solved either by commercial software package, such as CPLEX and LINGO, or by heuristics and metaheuristics. Since it is interesting to observe that similar solution techniques have been observed in the literature, that is, the majority of the resolution techniques applied in the field of scheduling are also applicable to the other two fields, we will do the survey from a general view rather than perform a dedicated survey in each field in order to reduce the redundant discussions.


## 3.1. Scheduling

Scheduling is generally used by managers to allocate necessary resources according to a given objective and the constraints. Optimization in scheduling plays an important role in both industrial and service domains because it can help decision-makers make a production/service scheduling with minimal cost or maximal output.The traditional quantitative notation used to describe a scheduling problem is proposed by Graham et al. [37]. They describe a scheduling problem by using the notation αβγ, where α defines the shop environment in terms of the setting and machine number; β defines some processing characteristics, such as shop condition and setup information; γ is used to describe the performance measure, that is, the objective function.According to the first field (α), the scheduling problems can be classified mainly into five categories:(i)
Single machine: only one machine is available for processing jobs (Cai et al. (2012); [38, 39]).(ii)
Parallel machine: a set of machines can start to process jobs simultaneously [40–42].(iii)
Flow shop: jobs are processed by a set of machines sequentially. The processing sequence of jobs through the machines must be the same [9, 43–45].(iv)
Job shop: jobs are processed by a set of machines and each job has a dedicated processing sequence; that is, the processing route of a job is not necessary to be the same with the others (Guo and Lei (2013) [46–51]).(v)
Open shop: jobs are processed by a set of machines. Different from flow shop and job shop where certain processing sequence is predefined for a job, there is no predetermined processing sequence for the jobs in open shop [52–54].With regard to the second field (β), some factors other than the processing sequence should be also considered:(1)
Wait between two consecutive operations of a job: if the no-wait constraint occurs, two successive operations of a job must be processed without any interruption and thus no-wait models are established in different environments: flow shop [55–60], hybrid/flexible workshop [61–65], job shop ([47, 66–68]), and open shop [47, 54, 69].(2)
Setup time: in traditional scheduling problems, the processing times of jobs are assumed to be fixed and independent constant values. However, in some case, a certain setup time is necessary for some on-process product to be ready for the next stage [70–73].(3)
Batch production: batch production, as an important processing way, exists in many scheduling environments [70–72, 74].The modelling of scheduling problems can also vary a lot in terms of the objective criteria, that is, the third field (γ). In fact, both single-objective scheduling and multicriteria problems have been widely studied in recent years. The single-objective problems are related just to one optimization criterion, while several optimal criteria are combined in the objective function of the multicriteria models.On the basis of the list of optimization criteria described in Section2, we have collected publications with the combination of key word “scheduling” and different optimal criteria. It is observed that the majority of the studies optimize the operations according to economic criteria and aim at maximizing economic performance. It is reasonable because both profit organizations and nonprofit organizations arrange the operations under limited budgets. It is worth mentioning that no significant differences were observed for economic and managerial criteria, whereas the number of the articles concerning societal criteria which have been published from the year 2010 onwards is about three times as great as those published before (as shown in Figure 1).Figure 1
Distribution of publications among three general optimization criteria before and from Y2010 onwards in the field of scheduling.As shown in Figure2, the economic criteria, such as completion time, makespan, and flow time, were mostly considered in studies both before and from the year 2010 onwards. Managerial criteria, such as tardiness, lateness, and earliness, were also widely considered though much fewer studies were dedicated to societal criteria.Figure 2
Proportion of the publications among different optimization criteria collected from the field of scheduling before and from Y2010 onwards.Furthermore, the comparison between the numbers of publications before and after the year 2010 (as shown in Figure3) reveals that an explosion can be observed in publications concerning energy cost, pollutant emission, and carbon emission; even they are only a very small part of the study on scheduling at present. It indicates that more and more OM researchers take into consideration both sustainable production and environment protection.Figure 3
Comparison between the numbers of publications before Y2010 and from Y2010 onwards in the field of scheduling.Furthermore, the limitation of resources also greatly influences the constructions of models. A detailed review of constraints influencing construction of scheduling models can be found in [43, 75, 76].


## 3.2. Rescheduling

Ideally, the working or service process will follow a given schedule that is optimally established at the stage of scheduling. However, in case a disturbance or a disruption occurs, the manufacturing or service system must be rescheduled because the predetermined schedule is no more feasible. In the manufacturing system, a machine disruption is said to occur when a machine becomes unavailable for some period of time for the sake of resource shortage, machine failure, or other unexpected reasons; sometimes, job disruptions can also happen when some parameters of a specific job change. Both machines failures and job disruptions can find their counterparts in service systems. For example, in the railway scheduling system, all disruptions related to trains or infrastructure can be regarded as machine disruptions though the disturbances caused by the passengers or customers can result in the so-called job disruptions. In general, a rescheduling problem inherits all the constraints from the original scheduling problem and takes into account the constraints raised from disturbances [77–80].In manufacturing domain, most of the rescheduling problems deal with machine disruptions [81–85] or machine breakdowns [86–92], while disturbances vary a lot in service industries. For example, in the transportation domain, disruptions may be caused by the delay of transportation tools [93–97]; in hospital, the arrival of emergency patients is the major reason for rescheduling [98, 99], while disruptions can be observed in computer system because of resource request failures [100, 101].Since each rescheduling problem can find its counterpart in the field of scheduling, the quantitative notation described in Section3.1 is also applicable to describing rescheduling problems. In fact, the main differences between scheduling and rescheduling are resulting from the objectives of the decision-makers.The distribution of optimization criteria employed in the field of rescheduling is quite different from that observed in the field of scheduling. As shown in Figure4, besides the criteria most frequently used for scheduling problems, schedule deviation, robustness, and equity have been also widely considered for rescheduling problems, especially in recent years.Figure 4
Distribution of the publications among different optimization criteria before and from Y2010 onwards in the field of rescheduling.According to the distribution of publications among different optimization criteria, as shown in Figure5, it is obvious that much more managerial and societal criteria are considered in rescheduling optimization; this phenomenon is due to the fact that most of the rescheduling problems are raised from the field of service managements, such as hospital management [102, 103] and transportation management [93, 96], where the requirements of the customers must also be considered.Figure 5
Distribution of publications among three general optimization criteria in the field of rescheduling before and from Y2010 onwards.


## 3.3. VRP

Starting with the study on truck dispatching problem published by Dantzig and Ramser [104] and the more generalized model developed by Clarke and Wright [105], a set of optimization problems that aim at finding an optimal way of serving a set of customers, geographically dispersed around the central depot, using a fleet of vehicles and taking into account necessary constraints, became known as the “vehicle routing problem” and became one of the most widely studied topics in the field of operations management. In recent years, its variants have grown ever more popular in the literature (as discussed by Gendreau et al. (2005a,b); Eksioglu et al. [106]; Braekers et al. [107]), though current models vary widely as more and more researchers aim to enable their models to cope with real-life complexities and the literature on vehicle routing problems has been growing exponentially at a rate of 6% each year [106, 107] and many surveys focused on specific variants can be observed as well [108–119].In general, the classical vehicle routing problem can be defined on a graphG=(V,A), where V={0,1,…,n} represents the node set that is corresponding to the depot and customers, and A=i,j∈V is set of arcs. The depot is noted as node 0 and customers are nodes j=1,2,…,n. An arc i,j∈A indicates a possible route that links nodes i and j and is associated with the cost of travelling Cij>0 from node i to node j. The vehicle routing problem is called symmetric if Cij=Cji; otherwise, it is called asymmetric [115]. A fleet of vehicles starts from a given depot to serve customers according to some predefined constraints. In general, the studies in vehicle routing problems aim to find a collection of circuits, each corresponding to a vehicle route with minimum cost, defined as the sum of the costs of the circuits’ arcs [106].In the literature, vehicle routing problems can be structured differently according to various constraints, such as capacitated VRP [120–126], the VRP with heterogeneous fleet of vehicles [127], open VRP [128–131], VRP with time windows [132–138], VPR with both pick-up and delivery [139–144], location routing problem [145–147], period VRP [148–151], multidepot VRP [152–156], VRP with backhaul [157–159], inventory routing problem [160–163], dynamic VRP [164], or the mixture [165–169].As for the definition of objective functions, both single-objective problems and multicriteria problems were widely studied in this field. Different from the studies about scheduling and rescheduling, where objective functions vary within a limited range, an interesting trend can be observed about the utilization of optimization criteria. Besides traditional economic criteria, whose meaning is similar to their counterparts in the field of scheduling and rescheduling, some other economic criteria were observed in this field:(i)
Travelling cost: this cost is associated with transportation distance or/and travelling time. This criterion is the mostly considered in the literature [133, 138, 160, 170–173];(ii)
Vehicle cost: this fixed operational cost is related to the number of vehicles. To the best of our knowledge, although some studies set the vehicle cost as their only objective [134, 144, 150, 174–178], the majority of the studies (54.3%) regard the vehicle cost as the part of fixed cost and aim to minimize the combination of the fixed cost with some variable costs, such as travelling cost [128, 133, 136, 145, 146, 179–183], penalty cost [184], inventory cost [163, 185–187], fuel cost [188], and emission [137].(iii)
Inventory cost: When integrating inventory management with vehicle routing decisions, the objective turns into not only minimizing the travelling cost or vehicle cost but also taking into consideration the inventory cost over the planning horizon [160–163, 165, 166, 185–187, 189–194].(iv)
Penalty cost: penalty costs are normally considered when the decision-makers want to make trade-off between positive and negative effects of diversions and enable an efficient application-dependent control of diversions [164]. In general, the penalty cost is raised from the punctuality of delivery [164, 182, 183, 195], the ability of meeting the demands [187, 189, 196], the capability of vehicles [184, 197], waste of product [193], congestion charge [198], and so forth.(v)
Fuel consumption: traditional vehicle routing problems often rely on costs related to transportation distance, inventory, or the fixed cost of vehicle usage; nowadays, more and more researchers try to minimize the total fuel consumption, which is not only influenced by distance or vehicles’ velocity but also related to the characteristics of each vehicle or even to the vehicle load [198–201]. In this study, this criterion is merged to the criterion “energy cost” so as to standardize the expression.(vi)
Driver cost: this cost is related mainly to the wage of the drivers and can be regarded as one important part of the fixed part of the total cost. Similar to the vehicle cost, driver cost is also determined by the number of vehicles employed [193, 195, 200, 202].(vii)
Loading/unloading cost: the loading/unloading cost is related to number of product units instead of the transportation distance. In some articles, the loading/unloading cost is considered as a part of the total operation cost [138, 160, 199, 203].(viii)
Service cost: this cost is paid for special services such as maintenance [163], opening depots [145, 146], construction of new locations [204].(ix)
Profit: profit is the most important objective of enterprises because efficient logistic operations can contribute a lot to the profits; many vehicle routing models were constructed with an objective to maximize the total expected profit ([205–207]; Kumar et al. (2017); [143]).Besides tardiness, earliness, lateness, and robustness, which can also be observed in the field of scheduling and rescheduling, some other managerial criteria were observed:(1)
Workload imbalance: ideally, vehicles that are responsible for the delivery of products along different routes should be charged similarly so as to improve the delivery efficiency. With this purpose, some studies tried to reduce the workload imbalance minimizing the travelling cost of the longest route [208–211] or balancing the daily workload [148].(2)
Coverage, that is, number of visited customers: in some variants of VRP where the assumption of visiting each customer does not hold, the maximization of the number of total visited customers is normally considered as the most important part of the objective because more customers visited show the higher efficiency of services [180, 212].Similar to scheduling and rescheduling problems, equity and emissions are also observed in the field of VRP when the decision-makers aim to build green logistic strategies, and thus the studies concerned with the reduction of emission have emerged in recent years [178, 180, 200, 213–215].As shown in Figures6 and 7, economic criteria, such as “travelling cost,” “penalty cost,” “energy cost,” and “profit,” greatly dominate the others. It is worth mentioning that except the observation of increasing attention paid to important economic criteria such as energy cost, penalty cost, and total profit of the operations, some societal criteria, such as robustness of the delivery and the emission of vehicles, began to draw more and more attentions. According to statistics, as shown in Figure 7, the portion of publications concerning societal criteria has increased from 7% to 10% since the year 2010.Figure 6
Distribution of publications among detailed optimization criteria in the field of VRP before and from Y2010 onwards.Figure 7
Distribution of publications among three general optimization criteria before and from Y2010 onwards in the field of VRP.To sum up, not only economic criteria but also managerial criteria and societal criteria were widely considered in the literature on OM optimization, though the economic ones were mostly considered both before and after the year 2010 in all targeted topics. Furthermore, we have observed that mathematical programming is widely used to construct quantitative models of the optimization problems, in all targeted fields, that will be solved either by commercial software package, such as CPLEX and LINGO, or by heuristics and metaheuristics. Since it is interesting to observe that similar solution techniques have been observed in the literature, that is, the majority of the resolution techniques applied in the field of scheduling are also applicable to the other two fields, we will do the survey from a general view rather than perform a dedicated survey in each field in order to reduce the redundant discussions.


## 4. Resolution Techniques

It can be observed that a plenty of methods have been developed to solve OM optimization problems. According to the literature, except constructive heuristics that are often dedicated to specific problems and cannot be used to solve other problems (as discussed by Mao et al. [86]; Mohapatra et al. [216]; Nourelfath [89]; Zachariadis et al. [139]; Kok et al. [217]; Kritikos and Ioannou [197]; López-Sánchez et al. [131]; Tiwari and Chang [214]; Nambirajan et al. [186]; Lin and Ying [218]), nearly each technique developed in one field and finds its counterpart in the others. In consequence, resolutions techniques are generally grouped according to their similarity. Furthermore, the techniques for tackling problems with uncertainty, especially the robustness optimization methods, will be discussed in a dedicated subsection.


### 4.1. Mathematical Programming-Based Approaches

In mathematical programming (MP), we seek to minimize or maximize an objective subject to a set of constraints. Except software package service as programming solver, MP-based approaches observed in the field of three targeted fields are as follows: Branch-and-Bound [34], Branch-and-Cut [146], Branch-and-Price [219], Branch-and-Cut-and-Price [142], Dynamic Programming [220], Lagrangian Relaxation [221], Column Generation [222], Set Partitioning [223], Constraint Programming [224], Goal Programming [225], Set Covering [226], and so forth.As shown in Table1, it can be observed that the most frequently used mathematical programming-based method in the field of scheduling is B&B (Branch-and-Bound), while B&P (Branch-and-Price) is the most popular branching method in the field of VRP. Quite few MP-based methods were applied to solving rescheduling problems. With a further analysis, we can conclude that Column Generation-related methods always draw the attentions of the researchers, and this may be explained by the fact that the efficiency of this kind of methods is much higher than that of the other branching methods. The abnormal absence of publications for rescheduling may be explained by the fact that the efficiency of MP-based algorithms is relatively low, while the response ability of the method is quite important for solving rescheduling problems.Table 1
Papers with mathematical programming-based methods before and from Y2010 onwards.
Before the year 2010
From the year 2010 onwards
Scheduling
Rescheduling
VRP
Scheduling
Rescheduling
VRP
B&P
13
0
3
23
0
16
B&C
9
0
7
8
0
10
B&B
89
0
2
70
3
1
B&P&C
1
0
5
1
0
15
CG
41
1
11
34
0
17
LR
9
0
2
2
0
1
SC
9
0
1
1
0
6
SP
2
0
4
2
0
4
DP
76
2
2
53
1
4
GP
16
1
1
19
0
2
CP
82
0
6
47
0
4
B&P: Branch-and-Price, B&C: Branch-and-Cut, B&B: Branch-and-Bound, B&P&C: Branch-and-Price-and-Cut; CG: Column Generation, LR: Lagrangian Relaxation, SC: Set Covering, SP: Set Partitioning, DP: Dynamic Programming, GP: Goal Programming; CP: Constraint Programming.


### 4.2. Metaheuristics

Metaheuristics are the strategies designed to guide the search process in order to find near-optimal solutions [227]. In the literature, metaheuristics are widely used to obtain good quality solutions within acceptable execution time and there exist already several surveys on metaheuristics [228, 229]. In this section, the survey on metaheuristics will be divided into three parts.


#### 4.2.1. Single-Solution-Based Metaheuristics

Simulated Annealing [230], Tabu Search [231], Greedy Algorithm [232], GRASP [233], Variable Neighborhood Search [234], Hill Climbing [235], and Iterated Local Search [158] are single-solution-based metaheuristics. As shown in Table 2, Simulated Annealing and Tabu Search are the two most popular single-solution-based metaheuristics for both scheduling and VRP. However, only four high-quality papers of rescheduling were observed from the year 2010 onwards. It is worth mentioning that the Greedy Algorithms were widely used in the field of scheduling, though only one paper from the field of VRP is found using this method.Table 2
Number of the publications concerned with single-solution-based metaheuristics that are published from Y2010 onwards.
Scheduling
Rescheduling
VRP
Simulated Annealing
101
0
16
Tabu Search
79
0
38
Greedy Algorithm
33
1
1
GRASP
23
3
10
Variable Neighborhood Search
53
0
42
Hill Climbing
4
0
0
Iterated Local Search
18
0
19
Total
311
4
126


#### 4.2.2. Population-Based Metaheuristics

Evolutionary Computation [236], Genetic Algorithm [187], Evolution Strategy [128], Evolutionary Programming [237], Genetic Programming [238], Estimation of Distribution Algorithm [35], Differential Evolution [239], Coevolutionary Algorithm [156], Scatter Search [50, 240], Swarm Intelligence [241], Ant Colony [242], Bacterial Foraging Optimization Algorithm [243], Bee Colony [244], Artificial Immune System [245], Particle Swarm Optimization [141], and Biogeography-based Optimization [246] are population-based metaheuristics.As shown in Table3, it can be concluded the following:(1)
Genetic Algorithm, Particle Swarm Optimization, and Ant Colony are the most popular metaheuristics in the field of scheduling.(2)
Differential Evolution and Bee Colony are also popular in the field of scheduling but not quite attractive to the researchers in the field of VRP.(3)
More applications of metaheuristics were observed in the field of rescheduling, whereas only a limited amount of papers could be observed in the literature. In fact, even fewer publications were published before the year of 2010.(4)
The majority of the metaheuristics have been developed in recent years. In fact, none of the mentioned metaheuristics was applied to tackling optimization problems in the field of scheduling before the year of 1990. Further, four of them, that is, Biogeography-based Optimization, Artificial Immune System, Bee Colony, and Bacterial Foraging Optimization algorithm, reported their first application in the field of scheduling no earlier than the year of 2010.Table 3
Number of the publications concerned with population-based metaheuristics that are published from Y2010 onwards.
Scheduling
Rescheduling
VRP
Evolutionary Computation
9
0
2
Genetic Algorithm
490
0
45
Evolution Strategy
2
1
2
Evolutionary Programming
9
0
0
Genetic Programming
15
0
0
Estimation of Distribution Algorithm
39
0
0
Differential Evolution
97
0
4
Coevolutionary Algorithm
8
0
3
Scatter Search
20
0
6
Swarm Intelligence
17
0
3
Ant Colony
149
2
33
Bacterial Foraging Optimization Algorithm
6
0
2
Bee Colony
71
1
8
Artificial Immune System
20
1
2
Particle Swarm Optimization
172
3
26
Biogeography-based Optimization
17
0
1
Total
1141
8
137


#### 4.2.3. Hybrid Metaheuristics

In recent years, besides newly proposed strategies of metaheuristics, many hybrid metaheuristics have been developed for improving either the efficiency of the algorithms or the quality of the final solutions, though there are fewer applications of hybrid metaheuristics than those of the other two types of metaheuristics (about 176 high-quality journal papers have been published on hybrid metaheuristics from the year of 2010 onwards).According to the literature, about one-half of the hybrid metaheuristics are based on the framework of Genetic Algorithm. Some studies used tailor-made genetic operators to enhance the ability of Genetic Algorithms (as discussed by Amin-Naseri and Afshari [247], Qing-Dao-Er-Ji and Wang [248, 249], Qing-Dao-Er-Ji et al. [250, 251], and Ahmadizar and Farahani [52]); Ahmad et al. [252] applied a problem-specific heuristic to improve the quality of initial solution; some other studies hybridized the Genetic Algorithm and some problem-specific local search schemes (as discussed by Do Ngoc et al. [253], Tseng and Lin [254], and Vidal et al. [135]) or neighborhood search procedures [255–257]. The majority of the hybrid methods are the combinations of different metaheuristics, such as the combination of Genetic Algorithm and Tabu Search procedures (as discussed by Zhang et al. [258], Meeran and Morshed [259], Li and Gao [260], Yu et al. [261], and Noori and Ghannadpour (2012)) and the integration of Genetic Algorithm and Simulated Annealing (as discussed by Safari and Sadjadi [262], Rafiei et al. [263], and Bettemir and Sonmez [264]). In recent years, the combination of Genetic Algorithm and Particle Swarm Optimization (PSO) had been widely applied in both scheduling and vehicle routing problems (as discussed by Du et al. [265], Yu et al. [266], Liu et al. [267], and Kumar and Vidyarthi [268]). Some other Genetic Algorithm-based hybrid methods were also observed in the literature, such as the hybrid Genetic-Monkey algorithm [269], hybrid Genetic Algorithm combined with the LP-relaxation of the targeted model (as discussed by Mohammad and Ghasem [270]), and the combination of Genetic Algorithm and Local Search procedure with Fuzzy Logic Control, where Fuzzy Logic Control is used to enhance the search ability of the Genetic Algorithm (as discussed by Chamnanlor et al. [271]); some Pareto-based hybrid Genetic Algorithms were also developed for dealing with multiobjective problems (as discussed by Zhang et al. [272] and Tao et al. [273]). Besides hybrid Genetic Algorithm, some other hybrid metaheuristics were observed in the literature, such as Greedy Randomized Adaptive Search Procedure (GRASP) enhanced with heuristic concentration (as discussed by Mendoza et al. 2016 [274]), Adaptive Local Search integrated with Tabu Search (as discussed by Avci and Topaloglu, 2016 [144]), and hybrid Ant Colony Optimization (ACO) procedure based on GRASP and VNS (as discussed by Brito et al. 2015 [275]). The integration of PSO and SA is also very encouraging (as discussed by Keshtzari et al. 2016 [276]). It is reasonable to conclude that the efficiency of population-based metaheuristics can be greatly improved by integrating either single-solution-based metaheuristics or problem-specific heuristics.


### 4.3. Optimization with Uncertainty

It is unavoidable that decision-makers must face a large amount of uncertainty involved in the operations management environment, such as unexpected breakdowns of machines and unstable travelling time of the vehicles. Therefore, the robustness has turned out to be one of the most important optimization criteria in recent years.Traditionally, decision problems with uncertainty are formulated as Markov decision processes or as stochastic programming. Markov decision processes are used rather for sensitivity analysis than for operations optimization. Whereas stochastic programming has been widely used to find a solution that is feasible for all (or almost all) instances of the uncertain inputs [277], it is quite complex because it not only needs a large amount of data but also requires too much time to obtain the output for the final solution, or it is even impossible to get the optimal one. Besides, some heuristics are developed as well to get robust solution against uncertainty. For example, Cui et al. [278] proposed two three-stage heuristic algorithms to find robust production and maintenance schedules for a single machine with failure uncertainty. According to the experimental results, the heuristics report better performance than the traditional one though it is quite essential for the authors to find the best trade-off between quality robustness and solution robustness because the difference between two heuristics is quite significant. According to a survey made by Cacchiani and Toth [279], which is dedicated to the train timetabling problem, a number of different approaches were applied for constructing robust timetables, including stochastic optimization, light robustness, recoverable robustness, delay management, bicriteria and Lagrangian-based approaches, and metaheuristics.Firstly proposed by Soyster [280] by using math set theory to describe uncertain information of the parameters, the robustness optimization method was normally designed to handle the problems that can be formulated as linear programming problems with uncertain parameters. This method assumes that the uncertain parameters reside with a deterministic “uncertainty set” in order to avoid big losses and it normally adopts a min-max approach that addresses data uncertainty by guaranteeing the feasibility and optimality of the solution against all instances of the parameters within the uncertainty set [281]. In recent years, the original version of robustness optimization method has been greatly improved by various researchers. For example, Ben-Tal et al. [282] proposed a paradigm termed as affinely adjustable robust counterpart (AARC) to restrict the adjustable variables to be in the form of affine function for multistage finite horizon problems whose deterministic version of the uncertain problem is linear programming. In the AARC method, the family of uncertain linear programs is replaced with a single tractable deterministic problem, which can be solved with deterministic approaches. The AARC method was applied to study the emergency vehicle routing scheduling problem under the uncertainty of travel time by Ben-Tal et al. [283]. The comparison between the results obtained by the robustness optimization method and those of the hybrid Particle Swarm Optimization (PSO) shows that the robustness optimization methods have better stability.As for rescheduling, Veelenturf et al. [284] proposed a quasi-robust rescheduling approach, based on the concept of recoverable robustness, for tackling a railway crew rescheduling problem. According to the results with the data collected from the railway system in Netherlands, where the number of drivers varied from 15 to 67, the quasi-robust rescheduling approach can obtain the final solution within 5 minutes, which is acceptable for a real-time application.The application of the robustness optimization method to VRP problems mainly starts from the year 2008, when Sungur et al. [285] firstly applied the robustness optimization method to tackle a capacitated vehicle routing problem with demand uncertainty; more and more researchers showed their interests in developing robust solutions against uncertainty in the field of VRP. For example, Ordonez [286] generalizes the model of Sungur et al. [285] to allow for upper bounds on the customer demands and travel times experienced by each vehicle. Gounaris et al. [287] considered a generic case where the customer demands are supported on polyhedron. They presented the condition under which the CVRP is reduced to a deterministic one and derived formulations for the generic case where different routes were suggested by the deterministic CVRP. Sun and Dong [57] adopted the conditional expectation of the total transportation costs as the optimization objective under the condition that the service capacity of the depot is maximized, so as to decrease the deviation in the expectation value of the optimization objective obtained under various possible events. Afterwards, this semideviation is substituted for robust measurement of combinatorial semideviation in their robustness optimization method. Gounaris et al. [288] proposed an adaptive memory programming (AMP) metaheuristic to tackle the CVRP with uncertain customer demand. Similar to population-based evolutionary algorithm, the AMP starts with initialization phase where some high-quality solutions are generated to construct the reference set. Once the initialization phase has been complete, a subset of the adaptive memory is selected as an intermediate solution from which the general of the final provisional solution is initiated. The provisional solution is then used to restart the Tabu Search algorithm and finally the best encountered feasible solution will be used to update the reference set. The comparison results between the AMP and the MILP solver (CPLEX 12.1) with 88 RCVRP benchmark instances, which have not been solved with global optimality by the original Branch-and-Cut scheme, show that the AMP is efficient for small- and medium-sized instances. More precisely, the numerical results demonstrated up to 483 customers and 38 vehicles, and the AMP has identified new best solution for 123 instances, that is quite encouraging.Since the number of publications is quite limited in terms of robustness, we will not conduct the distribution analysis in this section.


## 4.1. Mathematical Programming-Based Approaches

In mathematical programming (MP), we seek to minimize or maximize an objective subject to a set of constraints. Except software package service as programming solver, MP-based approaches observed in the field of three targeted fields are as follows: Branch-and-Bound [34], Branch-and-Cut [146], Branch-and-Price [219], Branch-and-Cut-and-Price [142], Dynamic Programming [220], Lagrangian Relaxation [221], Column Generation [222], Set Partitioning [223], Constraint Programming [224], Goal Programming [225], Set Covering [226], and so forth.As shown in Table1, it can be observed that the most frequently used mathematical programming-based method in the field of scheduling is B&B (Branch-and-Bound), while B&P (Branch-and-Price) is the most popular branching method in the field of VRP. Quite few MP-based methods were applied to solving rescheduling problems. With a further analysis, we can conclude that Column Generation-related methods always draw the attentions of the researchers, and this may be explained by the fact that the efficiency of this kind of methods is much higher than that of the other branching methods. The abnormal absence of publications for rescheduling may be explained by the fact that the efficiency of MP-based algorithms is relatively low, while the response ability of the method is quite important for solving rescheduling problems.Table 1
Papers with mathematical programming-based methods before and from Y2010 onwards.
Before the year 2010
From the year 2010 onwards
Scheduling
Rescheduling
VRP
Scheduling
Rescheduling
VRP
B&P
13
0
3
23
0
16
B&C
9
0
7
8
0
10
B&B
89
0
2
70
3
1
B&P&C
1
0
5
1
0
15
CG
41
1
11
34
0
17
LR
9
0
2
2
0
1
SC
9
0
1
1
0
6
SP
2
0
4
2
0
4
DP
76
2
2
53
1
4
GP
16
1
1
19
0
2
CP
82
0
6
47
0
4
B&P: Branch-and-Price, B&C: Branch-and-Cut, B&B: Branch-and-Bound, B&P&C: Branch-and-Price-and-Cut; CG: Column Generation, LR: Lagrangian Relaxation, SC: Set Covering, SP: Set Partitioning, DP: Dynamic Programming, GP: Goal Programming; CP: Constraint Programming.


## 4.2. Metaheuristics

Metaheuristics are the strategies designed to guide the search process in order to find near-optimal solutions [227]. In the literature, metaheuristics are widely used to obtain good quality solutions within acceptable execution time and there exist already several surveys on metaheuristics [228, 229]. In this section, the survey on metaheuristics will be divided into three parts.


### 4.2.1. Single-Solution-Based Metaheuristics

Simulated Annealing [230], Tabu Search [231], Greedy Algorithm [232], GRASP [233], Variable Neighborhood Search [234], Hill Climbing [235], and Iterated Local Search [158] are single-solution-based metaheuristics. As shown in Table 2, Simulated Annealing and Tabu Search are the two most popular single-solution-based metaheuristics for both scheduling and VRP. However, only four high-quality papers of rescheduling were observed from the year 2010 onwards. It is worth mentioning that the Greedy Algorithms were widely used in the field of scheduling, though only one paper from the field of VRP is found using this method.Table 2
Number of the publications concerned with single-solution-based metaheuristics that are published from Y2010 onwards.
Scheduling
Rescheduling
VRP
Simulated Annealing
101
0
16
Tabu Search
79
0
38
Greedy Algorithm
33
1
1
GRASP
23
3
10
Variable Neighborhood Search
53
0
42
Hill Climbing
4
0
0
Iterated Local Search
18
0
19
Total
311
4
126


### 4.2.2. Population-Based Metaheuristics

Evolutionary Computation [236], Genetic Algorithm [187], Evolution Strategy [128], Evolutionary Programming [237], Genetic Programming [238], Estimation of Distribution Algorithm [35], Differential Evolution [239], Coevolutionary Algorithm [156], Scatter Search [50, 240], Swarm Intelligence [241], Ant Colony [242], Bacterial Foraging Optimization Algorithm [243], Bee Colony [244], Artificial Immune System [245], Particle Swarm Optimization [141], and Biogeography-based Optimization [246] are population-based metaheuristics.As shown in Table3, it can be concluded the following:(1)
Genetic Algorithm, Particle Swarm Optimization, and Ant Colony are the most popular metaheuristics in the field of scheduling.(2)
Differential Evolution and Bee Colony are also popular in the field of scheduling but not quite attractive to the researchers in the field of VRP.(3)
More applications of metaheuristics were observed in the field of rescheduling, whereas only a limited amount of papers could be observed in the literature. In fact, even fewer publications were published before the year of 2010.(4)
The majority of the metaheuristics have been developed in recent years. In fact, none of the mentioned metaheuristics was applied to tackling optimization problems in the field of scheduling before the year of 1990. Further, four of them, that is, Biogeography-based Optimization, Artificial Immune System, Bee Colony, and Bacterial Foraging Optimization algorithm, reported their first application in the field of scheduling no earlier than the year of 2010.Table 3
Number of the publications concerned with population-based metaheuristics that are published from Y2010 onwards.
Scheduling
Rescheduling
VRP
Evolutionary Computation
9
0
2
Genetic Algorithm
490
0
45
Evolution Strategy
2
1
2
Evolutionary Programming
9
0
0
Genetic Programming
15
0
0
Estimation of Distribution Algorithm
39
0
0
Differential Evolution
97
0
4
Coevolutionary Algorithm
8
0
3
Scatter Search
20
0
6
Swarm Intelligence
17
0
3
Ant Colony
149
2
33
Bacterial Foraging Optimization Algorithm
6
0
2
Bee Colony
71
1
8
Artificial Immune System
20
1
2
Particle Swarm Optimization
172
3
26
Biogeography-based Optimization
17
0
1
Total
1141
8
137


### 4.2.3. Hybrid Metaheuristics

In recent years, besides newly proposed strategies of metaheuristics, many hybrid metaheuristics have been developed for improving either the efficiency of the algorithms or the quality of the final solutions, though there are fewer applications of hybrid metaheuristics than those of the other two types of metaheuristics (about 176 high-quality journal papers have been published on hybrid metaheuristics from the year of 2010 onwards).According to the literature, about one-half of the hybrid metaheuristics are based on the framework of Genetic Algorithm. Some studies used tailor-made genetic operators to enhance the ability of Genetic Algorithms (as discussed by Amin-Naseri and Afshari [247], Qing-Dao-Er-Ji and Wang [248, 249], Qing-Dao-Er-Ji et al. [250, 251], and Ahmadizar and Farahani [52]); Ahmad et al. [252] applied a problem-specific heuristic to improve the quality of initial solution; some other studies hybridized the Genetic Algorithm and some problem-specific local search schemes (as discussed by Do Ngoc et al. [253], Tseng and Lin [254], and Vidal et al. [135]) or neighborhood search procedures [255–257]. The majority of the hybrid methods are the combinations of different metaheuristics, such as the combination of Genetic Algorithm and Tabu Search procedures (as discussed by Zhang et al. [258], Meeran and Morshed [259], Li and Gao [260], Yu et al. [261], and Noori and Ghannadpour (2012)) and the integration of Genetic Algorithm and Simulated Annealing (as discussed by Safari and Sadjadi [262], Rafiei et al. [263], and Bettemir and Sonmez [264]). In recent years, the combination of Genetic Algorithm and Particle Swarm Optimization (PSO) had been widely applied in both scheduling and vehicle routing problems (as discussed by Du et al. [265], Yu et al. [266], Liu et al. [267], and Kumar and Vidyarthi [268]). Some other Genetic Algorithm-based hybrid methods were also observed in the literature, such as the hybrid Genetic-Monkey algorithm [269], hybrid Genetic Algorithm combined with the LP-relaxation of the targeted model (as discussed by Mohammad and Ghasem [270]), and the combination of Genetic Algorithm and Local Search procedure with Fuzzy Logic Control, where Fuzzy Logic Control is used to enhance the search ability of the Genetic Algorithm (as discussed by Chamnanlor et al. [271]); some Pareto-based hybrid Genetic Algorithms were also developed for dealing with multiobjective problems (as discussed by Zhang et al. [272] and Tao et al. [273]). Besides hybrid Genetic Algorithm, some other hybrid metaheuristics were observed in the literature, such as Greedy Randomized Adaptive Search Procedure (GRASP) enhanced with heuristic concentration (as discussed by Mendoza et al. 2016 [274]), Adaptive Local Search integrated with Tabu Search (as discussed by Avci and Topaloglu, 2016 [144]), and hybrid Ant Colony Optimization (ACO) procedure based on GRASP and VNS (as discussed by Brito et al. 2015 [275]). The integration of PSO and SA is also very encouraging (as discussed by Keshtzari et al. 2016 [276]). It is reasonable to conclude that the efficiency of population-based metaheuristics can be greatly improved by integrating either single-solution-based metaheuristics or problem-specific heuristics.


## 4.2.1. Single-Solution-Based Metaheuristics

Simulated Annealing [230], Tabu Search [231], Greedy Algorithm [232], GRASP [233], Variable Neighborhood Search [234], Hill Climbing [235], and Iterated Local Search [158] are single-solution-based metaheuristics. As shown in Table 2, Simulated Annealing and Tabu Search are the two most popular single-solution-based metaheuristics for both scheduling and VRP. However, only four high-quality papers of rescheduling were observed from the year 2010 onwards. It is worth mentioning that the Greedy Algorithms were widely used in the field of scheduling, though only one paper from the field of VRP is found using this method.Table 2
Number of the publications concerned with single-solution-based metaheuristics that are published from Y2010 onwards.
Scheduling
Rescheduling
VRP
Simulated Annealing
101
0
16
Tabu Search
79
0
38
Greedy Algorithm
33
1
1
GRASP
23
3
10
Variable Neighborhood Search
53
0
42
Hill Climbing
4
0
0
Iterated Local Search
18
0
19
Total
311
4
126


## 4.2.2. Population-Based Metaheuristics

Evolutionary Computation [236], Genetic Algorithm [187], Evolution Strategy [128], Evolutionary Programming [237], Genetic Programming [238], Estimation of Distribution Algorithm [35], Differential Evolution [239], Coevolutionary Algorithm [156], Scatter Search [50, 240], Swarm Intelligence [241], Ant Colony [242], Bacterial Foraging Optimization Algorithm [243], Bee Colony [244], Artificial Immune System [245], Particle Swarm Optimization [141], and Biogeography-based Optimization [246] are population-based metaheuristics.As shown in Table3, it can be concluded the following:(1)
Genetic Algorithm, Particle Swarm Optimization, and Ant Colony are the most popular metaheuristics in the field of scheduling.(2)
Differential Evolution and Bee Colony are also popular in the field of scheduling but not quite attractive to the researchers in the field of VRP.(3)
More applications of metaheuristics were observed in the field of rescheduling, whereas only a limited amount of papers could be observed in the literature. In fact, even fewer publications were published before the year of 2010.(4)
The majority of the metaheuristics have been developed in recent years. In fact, none of the mentioned metaheuristics was applied to tackling optimization problems in the field of scheduling before the year of 1990. Further, four of them, that is, Biogeography-based Optimization, Artificial Immune System, Bee Colony, and Bacterial Foraging Optimization algorithm, reported their first application in the field of scheduling no earlier than the year of 2010.Table 3
Number of the publications concerned with population-based metaheuristics that are published from Y2010 onwards.
Scheduling
Rescheduling
VRP
Evolutionary Computation
9
0
2
Genetic Algorithm
490
0
45
Evolution Strategy
2
1
2
Evolutionary Programming
9
0
0
Genetic Programming
15
0
0
Estimation of Distribution Algorithm
39
0
0
Differential Evolution
97
0
4
Coevolutionary Algorithm
8
0
3
Scatter Search
20
0
6
Swarm Intelligence
17
0
3
Ant Colony
149
2
33
Bacterial Foraging Optimization Algorithm
6
0
2
Bee Colony
71
1
8
Artificial Immune System
20
1
2
Particle Swarm Optimization
172
3
26
Biogeography-based Optimization
17
0
1
Total
1141
8
137


## 4.2.3. Hybrid Metaheuristics

In recent years, besides newly proposed strategies of metaheuristics, many hybrid metaheuristics have been developed for improving either the efficiency of the algorithms or the quality of the final solutions, though there are fewer applications of hybrid metaheuristics than those of the other two types of metaheuristics (about 176 high-quality journal papers have been published on hybrid metaheuristics from the year of 2010 onwards).According to the literature, about one-half of the hybrid metaheuristics are based on the framework of Genetic Algorithm. Some studies used tailor-made genetic operators to enhance the ability of Genetic Algorithms (as discussed by Amin-Naseri and Afshari [247], Qing-Dao-Er-Ji and Wang [248, 249], Qing-Dao-Er-Ji et al. [250, 251], and Ahmadizar and Farahani [52]); Ahmad et al. [252] applied a problem-specific heuristic to improve the quality of initial solution; some other studies hybridized the Genetic Algorithm and some problem-specific local search schemes (as discussed by Do Ngoc et al. [253], Tseng and Lin [254], and Vidal et al. [135]) or neighborhood search procedures [255–257]. The majority of the hybrid methods are the combinations of different metaheuristics, such as the combination of Genetic Algorithm and Tabu Search procedures (as discussed by Zhang et al. [258], Meeran and Morshed [259], Li and Gao [260], Yu et al. [261], and Noori and Ghannadpour (2012)) and the integration of Genetic Algorithm and Simulated Annealing (as discussed by Safari and Sadjadi [262], Rafiei et al. [263], and Bettemir and Sonmez [264]). In recent years, the combination of Genetic Algorithm and Particle Swarm Optimization (PSO) had been widely applied in both scheduling and vehicle routing problems (as discussed by Du et al. [265], Yu et al. [266], Liu et al. [267], and Kumar and Vidyarthi [268]). Some other Genetic Algorithm-based hybrid methods were also observed in the literature, such as the hybrid Genetic-Monkey algorithm [269], hybrid Genetic Algorithm combined with the LP-relaxation of the targeted model (as discussed by Mohammad and Ghasem [270]), and the combination of Genetic Algorithm and Local Search procedure with Fuzzy Logic Control, where Fuzzy Logic Control is used to enhance the search ability of the Genetic Algorithm (as discussed by Chamnanlor et al. [271]); some Pareto-based hybrid Genetic Algorithms were also developed for dealing with multiobjective problems (as discussed by Zhang et al. [272] and Tao et al. [273]). Besides hybrid Genetic Algorithm, some other hybrid metaheuristics were observed in the literature, such as Greedy Randomized Adaptive Search Procedure (GRASP) enhanced with heuristic concentration (as discussed by Mendoza et al. 2016 [274]), Adaptive Local Search integrated with Tabu Search (as discussed by Avci and Topaloglu, 2016 [144]), and hybrid Ant Colony Optimization (ACO) procedure based on GRASP and VNS (as discussed by Brito et al. 2015 [275]). The integration of PSO and SA is also very encouraging (as discussed by Keshtzari et al. 2016 [276]). It is reasonable to conclude that the efficiency of population-based metaheuristics can be greatly improved by integrating either single-solution-based metaheuristics or problem-specific heuristics.


## 4.3. Optimization with Uncertainty

It is unavoidable that decision-makers must face a large amount of uncertainty involved in the operations management environment, such as unexpected breakdowns of machines and unstable travelling time of the vehicles. Therefore, the robustness has turned out to be one of the most important optimization criteria in recent years.Traditionally, decision problems with uncertainty are formulated as Markov decision processes or as stochastic programming. Markov decision processes are used rather for sensitivity analysis than for operations optimization. Whereas stochastic programming has been widely used to find a solution that is feasible for all (or almost all) instances of the uncertain inputs [277], it is quite complex because it not only needs a large amount of data but also requires too much time to obtain the output for the final solution, or it is even impossible to get the optimal one. Besides, some heuristics are developed as well to get robust solution against uncertainty. For example, Cui et al. [278] proposed two three-stage heuristic algorithms to find robust production and maintenance schedules for a single machine with failure uncertainty. According to the experimental results, the heuristics report better performance than the traditional one though it is quite essential for the authors to find the best trade-off between quality robustness and solution robustness because the difference between two heuristics is quite significant. According to a survey made by Cacchiani and Toth [279], which is dedicated to the train timetabling problem, a number of different approaches were applied for constructing robust timetables, including stochastic optimization, light robustness, recoverable robustness, delay management, bicriteria and Lagrangian-based approaches, and metaheuristics.Firstly proposed by Soyster [280] by using math set theory to describe uncertain information of the parameters, the robustness optimization method was normally designed to handle the problems that can be formulated as linear programming problems with uncertain parameters. This method assumes that the uncertain parameters reside with a deterministic “uncertainty set” in order to avoid big losses and it normally adopts a min-max approach that addresses data uncertainty by guaranteeing the feasibility and optimality of the solution against all instances of the parameters within the uncertainty set [281]. In recent years, the original version of robustness optimization method has been greatly improved by various researchers. For example, Ben-Tal et al. [282] proposed a paradigm termed as affinely adjustable robust counterpart (AARC) to restrict the adjustable variables to be in the form of affine function for multistage finite horizon problems whose deterministic version of the uncertain problem is linear programming. In the AARC method, the family of uncertain linear programs is replaced with a single tractable deterministic problem, which can be solved with deterministic approaches. The AARC method was applied to study the emergency vehicle routing scheduling problem under the uncertainty of travel time by Ben-Tal et al. [283]. The comparison between the results obtained by the robustness optimization method and those of the hybrid Particle Swarm Optimization (PSO) shows that the robustness optimization methods have better stability.As for rescheduling, Veelenturf et al. [284] proposed a quasi-robust rescheduling approach, based on the concept of recoverable robustness, for tackling a railway crew rescheduling problem. According to the results with the data collected from the railway system in Netherlands, where the number of drivers varied from 15 to 67, the quasi-robust rescheduling approach can obtain the final solution within 5 minutes, which is acceptable for a real-time application.The application of the robustness optimization method to VRP problems mainly starts from the year 2008, when Sungur et al. [285] firstly applied the robustness optimization method to tackle a capacitated vehicle routing problem with demand uncertainty; more and more researchers showed their interests in developing robust solutions against uncertainty in the field of VRP. For example, Ordonez [286] generalizes the model of Sungur et al. [285] to allow for upper bounds on the customer demands and travel times experienced by each vehicle. Gounaris et al. [287] considered a generic case where the customer demands are supported on polyhedron. They presented the condition under which the CVRP is reduced to a deterministic one and derived formulations for the generic case where different routes were suggested by the deterministic CVRP. Sun and Dong [57] adopted the conditional expectation of the total transportation costs as the optimization objective under the condition that the service capacity of the depot is maximized, so as to decrease the deviation in the expectation value of the optimization objective obtained under various possible events. Afterwards, this semideviation is substituted for robust measurement of combinatorial semideviation in their robustness optimization method. Gounaris et al. [288] proposed an adaptive memory programming (AMP) metaheuristic to tackle the CVRP with uncertain customer demand. Similar to population-based evolutionary algorithm, the AMP starts with initialization phase where some high-quality solutions are generated to construct the reference set. Once the initialization phase has been complete, a subset of the adaptive memory is selected as an intermediate solution from which the general of the final provisional solution is initiated. The provisional solution is then used to restart the Tabu Search algorithm and finally the best encountered feasible solution will be used to update the reference set. The comparison results between the AMP and the MILP solver (CPLEX 12.1) with 88 RCVRP benchmark instances, which have not been solved with global optimality by the original Branch-and-Cut scheme, show that the AMP is efficient for small- and medium-sized instances. More precisely, the numerical results demonstrated up to 483 customers and 38 vehicles, and the AMP has identified new best solution for 123 instances, that is quite encouraging.Since the number of publications is quite limited in terms of robustness, we will not conduct the distribution analysis in this section.


## 5. Conclusions and Perspectives

In this paper, an overview of optimization modelling and resolution approaches in the field of operations management is given based on the recent literature, high-quality journal papers, published from 2010 to 2016, that were dedicated to three important topics of operations management: scheduling, rescheduling, and vehicle routing problems, which were selected from a process view.According to the literature, it is worthwhile underlining the following interesting phenomena:(1)
The economic criteria, such as completion time, makespan, and flow time, were mostly considered in the studies both before the year 2010 and from that year onwards. Managerial criteria, such as tardiness, lateness, and earliness, are also widely considered though much fewer studies are dedicated to societal criteria.(2)
An explosion can be observed in publications concerning energy cost, pollutant emission, and carbon emission; even they are only a very small part of the study of scheduling at present. It indicates that more and more OM researchers take into consideration both sustainable production and environment protection.(3)
Besides the criteria most frequently used for scheduling problems, schedule deviation, robustness, and equity have been also widely considered for rescheduling problems especially in recent years. In fact, much more managerial and societal criteria are considered in rescheduling optimization due to the fact that most of the rescheduling problems are raised from the field of service managements, where the requirements of the customers must also be considered.(4)
The most frequently used branching method in the field of scheduling is B&B (Branch-and-Bound), while B&P (Branch-and-Price) is the most popular branching method in the field of VRP. Neither mathematical programming-based methods nor metaheuristics were widely used in the field of rescheduling; in fact, only 16 articles were counted, though about 3945 high-quality papers were published from the year 2010. The abnormal absence of publications for rescheduling may be explained by the fact that the complexity of the working condition and the necessity of quick response push the decision-makers to make the decisions with their experiences or use efficient heuristics.(5)
Application of metaheuristics can be widely observed in the literature all along the operations management process. Some new metaheuristics have been developed in recent years, while some traditional metaheuristics are no more used though some analogies can be observed between the newly proposed metaheuristics and the traditional ones. Maybe it is important to improve the quality of the existing methods rather than propose new definitions. Hybridization of different methods could be a good direction to dive into.(6)
Many applications of hybrid metaheuristics in the field of OM were observed in the literature in recent years, half of which are Genetic Algorithm-based. It is encouraging that the efficiency of population-based metaheuristics can be greatly improved by integrating either single-solution-based metaheuristics or problem-specific heuristics.Except the studies of operations management in industrial fields, more and more studies were published on services management such as civil transportation management and healthcare management. The construction of optimization models for service management should rely more on the requirements of customers, making the optimization of service management quite different from that of the traditional operations management issues. Furthermore, most of the current studies are focused on deterministic environment, and very few of them contribute to improving the efficiency of effectiveness of operations in dynamic environment; it is worthwhile developing new models and methodologies that can help those decision-makers who are facing the uncertainty of the environment, to make robustness schedules or to quickly respond to the unexpected disturbance with a high-quality solution.



---

*Source: 7219656-2017-07-11.xml*