CPLEX中文教程(第七章)

第七章：IBM ILOG CPLEX在公交乘务排班优化问题中的应用

(一)公交乘务排班优化问题概述 公交乘务排班问题属活动资源的优化利用问题。一般是根据给定的乘务任务、乘务规则等条件，考虑一定的优化目标，对乘务员(组)的出乘时间、地点，担当的乘务任务、时刻，退乘时间、地点等做出具体安排，以确保一定周期内的所有乘务任务被执行。

第七章：IBM ILOG CPLEX在公交乘务排班优化问题中的应用公交乘务排班问题的基本元素和各元素的基本属性如下： 1)公交线路：具有出发站、出发时刻、到达站、到达时刻、中途停站等基本属性； 2)乘务员类型(组):包括司机、售票员等属性； 3)乘务规则：包括间休时间、工作时间、休息时间、乘务周期、月工时等乘务值乘规则。 4)目标函数:乘务成本最小、需要的乘务员数量最少等。 5)约束条件:乘务员的工作时间必须满足乘务规则；每个线路、每个班次都必须有乘务员值乘；乘务员劳动负衡均衡等约束条件。

第七章：IBM ILOG CPLEX在公交乘务排班优化问题中的应用例1.下面是某条线路的基本情况： 1、该线路的开收班时间：冬令(12月~3月):6:20~18:10,夏令(4月~11月):6:15~18:20 2、该线路的司机人数：15人 3、该线路排班间隔：平时：8~10分钟/班；上下班高峰(6:00~8:30,11:30~13:30,16:30~18:00):4~8分钟/班节假日：5~10分钟/班 4、该线路的运行时间：正常：80~85分钟/班高峰：100~120分钟/班规定：(1)司机每天上班时间不超过8小时；(2)司机连续开车不得超过4小时；(3)每名司机至少每月完成120班次。问题一：针对五月份的节假日和非节假日，分别求出每日最少班次总数；问题二：阐述你对上述规定的理解，并根据你的理解建立适当的数学模型，合理地设计五月份该线路的司机排班方案。

第七章：IBM ILOG CPLEX在公交乘务排班优化问题中的应用

(二)模型建立与求解1、问题一：数学模型的建立

(1)假设将非节假日一天的工作时间分为n个时段6

min Z=i=1

xi

k k xi mi Qi i 1 i 1 k k S .T . xi mi mk Qi i 1 i 1 8 mi 10 4 mi 8

k 1, 2, 3, 4, 5, 6. k 1, 2, 3, 4, 5, 6. i 2, 4, 6. i 1, 3, 5.

Qi——第i个时段的时长，i=1,2…,n mi——表示发车间隔； xi——表示发车班次用

第七章：IBM ILOG CPLEX在公交乘务排班优化问题中的应用问题一： 1、数学模型的建立 (2)若节假日，用Q表示节假日一天的工作时长，发车间隔用m表示，则例1中节假日最少班次的数学公式为：

Q min Z=, m

5≤ m≤ 10.

第七章：IBM ILOG CPLEX在公交乘务排班优

化问题中的应用问题一的模型文件：{string} Times={"T1","T2","T3","T4","T5","T6"}; float Q[Times]=[135, 180, 120, 180, 90, 20]; float m[Times]=[8, 10, 8, 10, 8, 10]; dvar int+ x[Times] in 0..50; minimize sum(o in Times) x[o]; subject to{ (x["T1"]-1)*m["T1"]<=Q["T1"]; Q["T1"]<=x["T1"]*m["T1"]; x["T1"]*m["T1"]+(x["T2"]-1)*m["T2"]<=Q["T1"]+Q["T2"]; Q["T1"]+Q["T2"]<=x["T1"]*m["T1"]+x["T2"]*m["T2"];

第七章：IBM ILOG CPLEX在公交乘务排班优化问题中的应用问题一的模型文件(续):x["T1"]*m["T1"]+x["T2"]*m["T2"]+(x["T3"]-1)*m["T3"]<=Q["T1"]+Q["T2"]+Q["T3"]; Q["T1"]+Q["T2"]+Q["T3"]<=x["T1"]*m["T1"]+x["T2"]*m["T2"]+x["T3"]*m["T3"]; x["T1"]*m["T1"]+x["T2"]*m["T2"]+x["T3"]*m["T3"]+(x["T4"]1)*m["T4"]<=Q["T1"]+Q["T2"]+Q["T3"]+Q["T4"]; Q["T1"]+Q["T2"]+Q["T3"]+Q["T4"]<=x["T1"]*m["T1"]+x["T2"]*m["T2"]+x["T3"]*m["T3"]+x["T 4"]*m["T4"]; x["T1"]*m["T1"]+x["T2"]*m["T2"]+x["T3"]*m["T3"]+x["T4"]*m["T4"]+(x["T5"]1)*m["T5"]<=Q["T1"]+Q["T2"]+Q["T3"]+Q["T4"]+Q["T5"]; Q["T1"]+Q["T2"]+Q["T3"]+Q["T4"]+Q["T5"]<=x["T1"]*m["T1"]+x["T2"]*m["T2"]+x["T3"]*m["T 3"]+x["T4"]*m["T4"]+x["T5"]*m["T5"]; x["T1"]*m["T1"]+x["T2"]*m["T2"]+x["T3"]*m["T3"]+x["T4"]*m["T4"]+x["T5"]*m["T5"]+(x["T6"]1)*m["T6"]<=Q["T1"]+Q["T2"]+Q["T3"]+Q["T4"]+Q["T5"]+Q["T6"]; Q["T1"]+Q["T2"]+Q["T3"]+Q["T4"]+Q["T5"]+Q["T6"]<=x["T1"]*m["T1"]+x["T2"]*m["T2"]+x["T 3"]*m["T3"]+x["T4"]*m["T4"]+x["T5"]*m["T5"]+x["T6"]*m["T6"];}

第七章：IBM ILOG CPLEX在公交乘务排班优化问题中的应用求解结果：高峰期(6:158:30)发车时间班次 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17平时(8:3011:30)发车时间 08:31 08:41 08:51 09:01 09:11 09:21 09:31 09:41 09:51 10:01 10:11 10:21 10:31 10:41 10:51 11:01 11:11 11:21班次 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35高峰期(11:3013:30)发车时间 11:31 11:39 11:47 11:55 12:03 12:11 12:19 12:27 12:35 12:43 12:51 12:59 13:07 13:15 13:23班次 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50平时(13:3016:30)发车时间 13:31 13:41 13:51 14:01 14:11 14:21 14:31 14:41 14:51 15:01 15:11 15:21 15:31 15:41 15:51 16:01 16:11 16:21班次 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68高峰期(16:3018:00)发车时间 16:31 16:39 16:47 16:55 17:03 17:11 17:19 17:27 17:35 17:43 17:51 17:59班次 69 70 71 72 73 74 75 76 77 78 79 80平时(18:0018:20)发车时间 18:07 18:17班次 81 82

// solution (optimal) with objective 82 x=[17 18 15 18 12 2]

06:15 06:23 06:31 06:39 06:47 06:55 07:03 07:11 07:19

据此，得到该线路非节假日的最少班次排班如右：

07:27 07:35 07:43 07:51 07:59 08:07 08:15 08:23

第七章：IBM ILOG CPLEX在公交乘务排班优化问题中的应用求解结果：发车时间班次 1 2 3 4 5 6 7 8 9 10 11 12发车时间 08:15 08:25 08:35 08:45 08:55 09:05 09:15 09:25 09:35 09:45 09:55 10:05班次 13 14 15 16 17 18 19 20 21 22 23 24时间(6:20-18:10)

发车时间 10:15 10:25 10:35 10:45 10:55 11:05 11:15

11:25 11:35 11:45 11:55 12:05

班次 25 26 27 28 29 30 31 32 33 34 35 36

发车时间 12:15 12:25 12:35 12:45 12:55 13:05 13:15 13:25 13:35 13:45 13:55 14:05

班次 37 38 39 40 41 42 43 44 45 46 47 48

发车时间 14:15 14:25 14:35 14:45 14:55 15:05 15:15 15:25 15:35 15:45 15:55 16:05

班次 49 50 51 52 53 54 55 56 57 58 59 60

发车时间 16:15 16:25 16:35 16:45 16:55 17:05 17:15 17:25 17:35 17:45 17:55 18:05 18:15

班次 61 62 63 64 65 66 67 68 69 70 71 72 73

节假日的最少班次排班如右：

06:15 06:25 06:35 06:45 06:55 07:05 07:15 07:25 07:35 07:45 07:55 08:05

第七章：IBM ILOG CPLEX在公交乘务排班优化问题中的应用问题二： 1、数学模型的建立 (1)非节假日

目标函数：min约束条件：

Xj j 1

19

式中： ai——表示非节假日一天内第i个司机工作的高峰班次数 bi——表示非节假日一天内第i个司机工作的非高峰班次数 xj——表示司机排班情况

(aij 1 19 j 1

19

xj) 44

(bi xj) 38

第七章：IBM ILOG CPLEX在公交乘务排班优化问题中的应用

司机排班情况

第七章：IBM ILOG CPLEX在公交乘务排班优化问题中的应用模型编码：{string} Categories={"C1","C2","C3","C4","C5","C6","C7","C8","C9","C10","C11","C12","C13","C14","C15","C16","C17","C18","C19"}; int a[Categories]=[0, 0, 0, 0, 0, 1, 1, 1, 1, 1, 2, 2, 2, 2, 3, 3, 3, 4, 4]; int b[Categories]=[1, 2, 3, 4, 5, 0, 1, 2, 3, 4, 0, 1, 2, 3, 0, 1, 2, 0, 1]; dvar int+ x[Categories] in 0..50; minimize sum(o in Categories) x[o]; subject to{ sum( o in Categories ) a[o]*x[o]== 44; sum( o in Categories ) b[o]*x[o]== 38;}

第七章：IBM ILOG CPLEX在公交乘务排班优化问题中的应用求解结果：// solution (optimal) with objective 17 x=[0 1 0 0 5 0 0 0 0 0 0 0 0 0 0 0 0 0 11]

该结果给出了一天需要的最少司机人数为17人，同时给出了一个可行的排班方案，即17位司机中，有1位采用第2种排班情况，有5位采用第5种

排班情况，有11位采用第19种排班情况。

第七章：IBM ILOG CPLEX在公交乘务排班优化问题中的应用问题二： 1、数学模型的建立 (1)节假日对于节假日，通过问题一可以求解出一天内总班次为73;

ci 73;i 1

R2

式中： ci——节假日一天内第i个司机工作的班次数 T2——节假日所有汽车运行时间之和 R2——节假日一天内需要的最少司机人数

80ci 480;

T 2 73 80;R2 13因为R 2 T 2/ 480所以R2 13

第七章：IBM ILOG CPLEX在公交乘务排班优化问题中的应用节假日一天的司机安排表：

本文来源：https://www.bwwdw.com/article/xocj.html