校车运输空返问题

2023-11-29 12:29:40

校车运输空返问题

记录2021年“工大出版社”数学建模竞赛A题的代码求解

背景

某学校每天有教职工从老校区乘车到新校区工作，工作后大多数人会返回。后勤集团每天会安排车辆在新老校区之间往返运行。但某些时段新老校区需要乘车的人数不均衡，如早上主要是老校区的教职工乘车到新校区，中午和下午下班时主要是教职工从老校区返回新校区。由于车辆有限，有时候为了满足当前校区车辆的需求，需要从另一校区调度空车返回（称为空返）。如何使空返的车辆数尽量少是后勤集团十分关心的问题。
该校班车运行时刻表如下：
一、周一至周五

  1. 老校区到新校区
    7:00，8:00，9:20、10:00、11:00、12:00、12:50、14:00、14:50、16:00、17:00、17:50、21:00、22:30。

  2. 新校区到老校区
    9:00、10:30、11:00、12:30、14:00、15:00、16:00、17:10、18:00、19:00、21:00、22:30。
    二、周六、周日

  3. 老校区到新校区
    8:00、9:20、12:50、14:00、18:00、20:00。

  4. 新校区到老校区
    9:00、 11:00、12:30、17:00、18:00、21:00。

    车辆在两校区运行时间时间为一个小时左右。为简化起见，假设每辆车从一个校区到另一个校区的时间都为一个小时。由于两校区不同时刻对车辆的需求不平衡，当某个校区需要的车辆数多，现有车辆不能满足需求，这时需要从另一个校区调度空车返回。空车可以在现有发车时刻表中某一时刻发车，也可以在需要的时候提前一个小时发车。
    该校总共有车辆20辆，每辆可载客人47人。请你建立数学模型仔细考虑下面问题。

模型概述

本道题一以贯之的是一个整数规划模型，决策变量为所有发车时刻的实际发车数和初始时刻两校区的校车数。目标函数则是空返车数，空返车数实际上就是实际发车数减去目标发车数。再对每个时刻求和。

题目

问题1

若某天（周一到周五）老校区到新校区对应14个发车时刻需要的车辆数为7、6、4、3、1、1、4、3、1、2、1、2、1、1；新校区到老校区需要的车辆数为2、3、2、6、2、1、7、6、4、2、1、1。通过计算探究能否实现车辆不空载。若能实现，给出车辆安排方式；若一定会出现空载，那么如何安排可使空返车辆数最少？若老校区到新校区需要车辆数为9、8、4、3、1、1、4、3、1、2、1、2、1、1，新校区到老校区需要的车辆数为3、4、2、6、2、1、7、8、4、2、1、1，情况又如何？请给出初始两校区车辆数，当天停止运行后两校区车辆数，总的空返车辆数。

Lingo代码：
在一二小问切换时，只需要讲target的注释修改即可。

MODEL:
!定义集合;
SETS:
new/1..12/:new_school,new_time,target_new;
old/1..14/:old_school,old_time,target_old;
un/1..11/;
uo/1..13/;
initial/1/:old_init_num;
ENDSETS
DATA:
new_time=9,10.5,11,12.5,14,15,16,17,18,19,21,22.5;
old_time=7,8,9.3333,10,11,12,12.8333,14,14.8333,16,17,17.8333,21,22.5;
target_new=3,4,2,6, 2,1,7,8, 4,2,1,1;
target_old=9,8,4,3,1,1,4,3,1,2,1,2,1,1;
!target_new=2,3,2,6, 2,1,7,6, 4,2,1,1;
!target_old=7,6,4,3,1,1,4,3,1,2,1,2,1,1;
@ole('C://Users//86183//Desktop//output1_1.xlsx','A')=new_school;
@ole('C://Users//86183//Desktop//output1_1.xlsx','B')=old_school;
@ole('C://Users//86183//Desktop//output1_1.xlsx','S')=old_init_num;
ENDDATA
min=@sum(new(i):(new_school(i)-target_new(i)))+@sum(old(i):(old_school(i)-target_old(i)));
@for(initial(i):
	old_init_num(i)>=old_school(1)+old_school(2);
	old_init_num(i)>=0;
	old_init_num(i)<=20;
);
@for(new(i):
	new_school(i)>=target_new(i)
);
@for(old(i):
	old_school(i)>=target_old(i)
);
@for(new(i):
	@for(uo(j)|(old_time(j)+1)#le#new_time(i) #and# new_time(i)#lt#(old_time(j+1)+1):
			(20-old_init_num(1))+(@sum(old(k)|k#le#j:old_school(k))-@sum(new(k)|k#lt#i:new_school(k)))>=new_school(i)
	)
);
@for(old(i)|i#ge#3:
	@for(un(j)|(new_time(j)+1)#le#old_time(i) #and# old_time(i)#lt#(new_time(j+1)+1):
			old_init_num(1)+(@sum(new(k)|k#le#j:new_school(k))-@sum(old(k)|k#lt#i:old_school(k)))>=old_school(i)
	)
);
@for(new(i):
	@gin(new_school(i))
);
@for(old(i):
	@gin(old_school(i))
);

最终解得：
校车运输空返问题
对于问题1第2小问，最少的空返数是5。

问题2

如果保持每天连续运行，每天老校区各班次需要车辆数仍为9,8,4,3,1,1,4,3,1,2,1,2,1,1；新校区各班次需要的车辆仍为3,4,2,6, 2,1,7,8, 4,2,1,1，问如何安排可使一周（周一到周五）空返车辆数总数最少？
要求给出周一初始两校区车辆数，周五停止运行后两校区车辆数，总的空返车辆数。

Lingo代码：

MODEL:
!定义集合;
SETS:
new/1..12/:new_time,target_new;
old/1..14/:old_time,target_old;
un/1..11/;
uo/1..13/;
initial/1..5/:old_init_num;
days/1..5/;
dayso/1..4/;
newweek(days,new):new_school;
oldweek(days,old):old_school;
ENDSETS
DATA:
new_time=9,10.5,11,12.5,14,15,16,17,18,19,21,22.5;
old_time=7,8,9.3333,10,11,12,12.8333,14,14.8333,16,17,17.8333,21,22.5;
target_new=3,4,2,6, 2,1,7,8, 4,2,1,1;
target_old=9,8,4,3,1,1,4,3,1,2,1,2,1,1;
@ole('C:\Users\86183\Desktop\output2.xlsx','q')=new_school;
@ole('C:\Users\86183\Desktop\output2.xlsx','w')=old_school;
@ole('C:\Users\86183\Desktop\output2.xlsx','e')=old_init_num;
ENDDATA
min=@sum(newweek(i,j):(new_school(i,j)-target_new(j)))+@sum(oldweek(i,j):(old_school(i,j)-target_old(j)));
@for(initial(i):
	old_init_num(i)>=old_school(i,1)+old_school(i,2);
	old_init_num(i)>=0;
	old_init_num(i)<=20;
);
@for(newweek(i,j):
	new_school(i,j)>=target_new(j)
);
@for(oldweek(i,j):
	old_school(i,j)>=target_old(j)
);
!对于新校区;
@for(days(i):
	@for(new(j):
		@for(uo(n)|(old_time(n)+1)#le#new_time(j) #and# new_time(j)#lt#(old_time(n+1)+1):
		(20-old_init_num(i))+@sum(old(k)|k#le#n:old_school(i,k))-@sum(new(k)|k#lt#j:new_school(i,k))>=new_school(i,j)
		)
	)
);
!对于老校区;
@for(days(i):
	@for(old(j)|j#ge#3:
		@for(un(n)|(new_time(n)+1)#le#old_time(j) #and# old_time(j)#lt#(new_time(n+1)+1):
		old_init_num(i)+@sum(new(s)|s#le#n:new_school(i,s))-@sum(old(s)|s#lt#j:old_school(i,s))>=old_school(i,j)
		)
	)
);
@for(dayso(i):old_init_num(i+1)=old_init_num(i)
			-@sum(old(j):old_school(i,j))
			+@sum(new(j):new_school(i,j))
);
@for(newweek(i,j):
	@gin(new_school(i,j))
);
@for(oldweek(i,j):
	@gin(old_school(i,j))
);

最终解得：
校车运输空返问题

对于问题2，最少的空返数是29。

问题3

若周六老校区各班次需要车辆数为：5,4,6,4,3,2；新校区为：3,5,7,6,2,1。周日老校区各班次需要车辆数为：5,4,4,6,3,7；新校区为：2,6,5,3,3,1。考虑周一到周日共7天，如何安排使空返车辆数最少？
要求给出周一初始两校区车辆数，周日停止运行后两校区车辆数，总的空返车辆数。

Lingo代码：

MODEL:
!定义集合;
SETS:
new/1..12/:new_time,target_new;
old/1..14/:old_time,target_old;
sat_new/1..6/:new_sat_time,target_new_sat,new_school_sat;
sat_old/1..6/:old_sat_time,target_old_sat,old_school_sat;
sun_new/1..6/:new_sun_time,target_new_sun,new_school_sun;
sun_old/1..6/:old_sun_time,target_old_sun,old_school_sun;
un/1..11/;
uo/1..13/;
un_weekend/1..5/;
uo_weekend/1..5/;
initial/1..7/:old_init_num;
days/1..5/;
dayso/1..4/;
sat/1/;
sun/1/;
newweek(days,new):new_school;
oldweek(days,old):old_school;
ENDSETS
DATA:
new_time=9,10.5,11,12.5,14,15,16,17,18,19,21,22.5;
old_time=7,8,9.3333,10,11,12,12.8333,14,14.8333,16,17,17.8333,21,22.5;
new_sat_time=9,11,12.5,17,18,21;
old_sat_time=8,9.3333,12.8333,14,18,20;
new_sun_time=9,11,12.5,17,18,21;
old_sun_time=8,9.3333,12.8333,14,18,20;
target_new=3,4,2,6, 2,1,7,8, 4,2,1,1;
target_old=9,8,4,3,1,1,4,3,1,2,1,2,1,1;
target_new_sat=3,5,7,6,2,1;
target_old_sat=5,4,6,4,3,2;
target_new_sun=2,6,5,3,3,1;
target_old_sun=5,4,4,6,3,7;
@ole('C:\Users\86183\Desktop\output3.xlsx','q')=new_school;
@ole('C:\Users\86183\Desktop\output3.xlsx','w')=old_school;
@ole('C:\Users\86183\Desktop\output3.xlsx','e')=old_init_num;
@ole('C:\Users\86183\Desktop\output3.xlsx','a')=new_school_sat;
@ole('C:\Users\86183\Desktop\output3.xlsx','s')=old_school_sat;
@ole('C:\Users\86183\Desktop\output3.xlsx','d')=new_school_sun;
@ole('C:\Users\86183\Desktop\output3.xlsx','f')=old_school_sun;
ENDDATA
min=@sum(newweek(i,j):(new_school(i,j)-target_new(j)))+@sum(oldweek(i,j):(old_school(i,j)-target_old(j))) + 
	@sum(sat_new(i):(new_school_sat(i)-target_new_sat(i))) + @sum(sat_old(i):(old_school_sat(i)-target_old_sat(i)))+
	@sum(sun_new(i):(new_school_sun(i)-target_new_sun(i))) + @sum(sun_old(i):(old_school_sun(i)-target_old_sun(i)))	
;
@for(initial(i)|i#le#5:
	old_init_num(i)>=old_school(i,1)+old_school(i,2);
	old_init_num(i)>=0;
	old_init_num(i)<=20;
);
@for(initial(i)|i#eq#6:
	old_init_num(i)>=old_school_sat(1);
	old_init_num(i)>=0;
	old_init_num(i)<=20;
);
@for(initial(i)|i#eq#7:
	old_init_num(i)>=old_school_sun(1);
	old_init_num(i)>=0;
	old_init_num(i)<=20;
);
@for(newweek(i,j):
	new_school(i,j)>=target_new(j)
);
@for(oldweek(i,j):
	old_school(i,j)>=target_old(j)
);

@for(sat_new(i):
	new_school_sat(i)>=target_new_sat(i)
);
@for(sat_old(i) :
	old_school_sat(i)>=target_old_sat(i)
);

@for(sun_new(i):
	new_school_sun(i)>=target_new_sun(i)
);
@for(sun_old(i) :
	old_school_sun(i)>=target_old_sun(i)
);
!对于新校区;
@for(days(i):
	@for(new(j):
		@for(uo(n)|(old_time(n)+1)#le#new_time(j) #and# new_time(j)#lt#(old_time(n+1)+1):
		(20-old_init_num(i))+@sum(old(k)|k#le#n:old_school(i,k))-@sum(new(k)|k#lt#j:new_school(i,k))>=new_school(i,j)
		)
	)
);
@for(sat_new(i):
	@for(uo_weekend(j)|(old_sat_time(j)+1)#le#new_sat_time(i) #and# new_sat_time(i) #lt#(old_sat_time(j+1)+1):
	(20-old_init_num(6))+@sum(sat_old(k)|k#le#j:old_school_sat(k))-@sum(sat_new(k)|k #lt#i:new_school_sat(k))>=new_school_sat(i)
	)
);
@for(sun_new(i):
	@for(uo_weekend(j)|(old_sun_time(j)+1)#le#new_sun_time(i) #and# new_sun_time(i) #lt#(old_sun_time(j+1)+1):
	(20-old_init_num(7))+@sum(sun_old(k)|k#le#j:old_school_sun(k))-@sum(sun_new(k)|k #lt#i:new_school_sun(k))>=new_school_sun(i)
	)
);
!对于老校区;
@for(days(i):
	@for(old(j)|j#ge#3:
		@for(un(n)|(new_time(n)+1)#le#old_time(j) #and# old_time(j)#lt#(new_time(n+1)+1):
		old_init_num(i)+@sum(new(s)|s#le#n:new_school(i,s))-@sum(old(s)|s#lt#j:old_school(i,s))>=old_school(i,j)
		)
	)
);
@for(sat_old(i)|i#ge#2:
	@for(un_weekend(j)|(new_sat_time(j)+1)#le#old_sat_time(i) #and# old_sat_time(i)#lt#(new_sat_time(j+1)+1):
	old_init_num(6)+(@sum(sat_new(k)|k#le#j:new_school_sat(k))-@sum(sat_old(k)|k#lt#i:old_school_sat(k)))>=old_school_sat(i)
	)
);

@for(sun_old(i)|i#ge#2:
	@for(un_weekend(j)|(new_sun_time(j)+1)#le#old_sun_time(i) #and# old_sun_time(i)#lt#(new_sun_time(j+1)+1):
	old_init_num(7)+(@sum(sun_new(k)|k#le#j:new_school_sun(k))-@sum(sun_old(k)|k#lt#i:old_school_sun(k)))>=old_school_sun(i)
	)
);

@for(dayso(i):old_init_num(i+1)=old_init_num(i)
			-@sum(old(j):old_school(i,j))
			+@sum(new(j):new_school(i,j))
);
@for(sat(i):old_init_num(i+5)=old_init_num(5)
			-@sum(old(j):old_school(5,j))
			+@sum(new(j):new_school(5,j))
);
@for(sun(i):old_init_num(i+6)=old_init_num(6)
					-@sum(sat_old(j):old_school_sat(j))
					+@sum(sat_new(j):new_school_sat(j))
);

@for(newweek(i,j):
	@gin(new_school(i,j))
);
@for(oldweek(i,j):
	@gin(old_school(i,j))
);
@for(sat_new(i):
	@gin(new_school_sat(i));
);
@for(sat_old(i):
	@gin(old_school_sat(i));
);
@for(sun_new(i):
	@gin(new_school_sun(i));
);
@for(sun_old(i):
	@gin(old_school_sun(i));
);

最终解得：
校车运输空返问题
对于问题3，最少的空返数是34。

问题4

在实际车辆调度中，希望每周能持续运行。在问题3的要求下，若再要求周日停止运行后两校区的车辆数与周一初始两校区车辆数相同，如何安排使空返车辆数最少？
要求给出周一初始两校区车辆数或周日停止运行后两校区车辆数，总的空返车辆数。

Lingo代码：

MODEL:
!定义集合;
SETS:
new/1..12/:new_time,target_new;
old/1..14/:old_time,target_old;
sat_new/1..6/:new_sat_time,target_new_sat,new_school_sat;
sat_old/1..6/:old_sat_time,target_old_sat,old_school_sat;
sun_new/1..6/:new_sun_time,target_new_sun,new_school_sun;
sun_old/1..6/:old_sun_time,target_old_sun,old_school_sun;
un/1..11/;
uo/1..13/;
un_weekend/1..5/;
uo_weekend/1..5/;
initial/1..8/:old_init_num;
days/1..5/;
dayso/1..4/;
sat/1/;
sun/1/;
mon/1/;
newweek(days,new):new_school;
oldweek(days,old):old_school;
ENDSETS
DATA:
new_time=9,10.5,11,12.5,14,15,16,17,18,19,21,22.5;
old_time=7,8,9.3333,10,11,12,12.8333,14,14.8333,16,17,17.8333,21,22.5;
new_sat_time=9,11,12.5,17,18,21;
old_sat_time=8,9.3333,12.8333,14,18,20;
new_sun_time=9,11,12.5,17,18,21;
old_sun_time=8,9.3333,12.8333,14,18,20;
target_new=3,4,2,6, 2,1,7,8, 4,2,1,1;
target_old=9,8,4,3,1,1,4,3,1,2,1,2,1,1;
target_new_sat=3,5,7,6,2,1;
target_old_sat=5,4,6,4,3,2;
target_new_sun=2,6,5,3,3,1;
target_old_sun=5,4,4,6,3,7;
@ole('C:\Users\86183\Desktop\output4.xlsx','q')=new_school;
@ole('C:\Users\86183\Desktop\output4.xlsx','w')=old_school;
@ole('C:\Users\86183\Desktop\output4.xlsx','e')=old_init_num;
@ole('C:\Users\86183\Desktop\output4.xlsx','a')=new_school_sat;
@ole('C:\Users\86183\Desktop\output4.xlsx','s')=old_school_sat;
@ole('C:\Users\86183\Desktop\output4.xlsx','d')=new_school_sun;
@ole('C:\Users\86183\Desktop\output4.xlsx','f')=old_school_sun;
ENDDATA
min=@sum(newweek(i,j):(new_school(i,j)-target_new(j)))+@sum(oldweek(i,j):(old_school(i,j)-target_old(j))) + 
	@sum(sat_new(i):(new_school_sat(i)-target_new_sat(i))) + @sum(sat_old(i):(old_school_sat(i)-target_old_sat(i)))+
	@sum(sun_new(i):(new_school_sun(i)-target_new_sun(i))) + @sum(sun_old(i):(old_school_sun(i)-target_old_sun(i)))	
;
@for(initial(i)|i#le#5:
	old_init_num(i)>=old_school(i,1)+old_school(i,2);
	old_init_num(i)>=0;
	old_init_num(i)<=20;
);
@for(initial(i)|i#eq#6:
	old_init_num(i)>=old_school_sat(1);
	old_init_num(i)>=0;
	old_init_num(i)<=20;
);
@for(initial(i)|i#eq#7:
	old_init_num(i)>=old_school_sun(1);
	old_init_num(i)>=0;
	old_init_num(i)<=20;
);
@for(newweek(i,j):
	new_school(i,j)>=target_new(j)
);
@for(oldweek(i,j):
	old_school(i,j)>=target_old(j)
);

@for(sat_new(i):
	new_school_sat(i)>=target_new_sat(i)
);
@for(sat_old(i) :
	old_school_sat(i)>=target_old_sat(i)
);

@for(sun_new(i):
	new_school_sun(i)>=target_new_sun(i)
);
@for(sun_old(i) :
	old_school_sun(i)>=target_old_sun(i)
);
!对于新校区;
@for(days(i):
	@for(new(j):
		@for(uo(n)|(old_time(n)+1)#le#new_time(j) #and# new_time(j)#lt#(old_time(n+1)+1):
		(20-old_init_num(i))+@sum(old(k)|k#le#n:old_school(i,k))-@sum(new(k)|k#lt#j:new_school(i,k))>=new_school(i,j)
		)
	)
);
@for(sat_new(i):
	@for(uo_weekend(j)|(old_sat_time(j)+1)#le#new_sat_time(i) #and# new_sat_time(i) #lt#(old_sat_time(j+1)+1):
	(20-old_init_num(6))+@sum(sat_old(k)|k#le#j:old_school_sat(k))-@sum(sat_new(k)|k #lt#i:new_school_sat(k))>=new_school_sat(i)
	)
);
@for(sun_new(i):
	@for(uo_weekend(j)|(old_sun_time(j)+1)#le#new_sun_time(i) #and# new_sun_time(i) #lt#(old_sun_time(j+1)+1):
	(20-old_init_num(7))+@sum(sun_old(k)|k#le#j:old_school_sun(k))-@sum(sun_new(k)|k #lt#i:new_school_sun(k))>=new_school_sun(i)
	)
);
!对于老校区;
@for(days(i):
	@for(old(j)|j#ge#3:
		@for(un(n)|(new_time(n)+1)#le#old_time(j) #and# old_time(j)#lt#(new_time(n+1)+1):
		old_init_num(i)+@sum(new(s)|s#le#n:new_school(i,s))-@sum(old(s)|s#lt#j:old_school(i,s))>=old_school(i,j)
		)
	)
);
@for(sat_old(i)|i#ge#2:
	@for(un_weekend(j)|(new_sat_time(j)+1)#le#old_sat_time(i) #and# old_sat_time(i)#lt#(new_sat_time(j+1)+1):
	old_init_num(6)+(@sum(sat_new(k)|k#le#j:new_school_sat(k))-@sum(sat_old(k)|k#lt#i:old_school_sat(k)))>=old_school_sat(i)
	)
);

@for(sun_old(i)|i#ge#2:
	@for(un_weekend(j)|(new_sun_time(j)+1)#le#old_sun_time(i) #and# old_sun_time(i)#lt#(new_sun_time(j+1)+1):
	old_init_num(7)+(@sum(sun_new(k)|k#le#j:new_school_sun(k))-@sum(sun_old(k)|k#lt#i:old_school_sun(k)))>=old_school_sun(i)
	)
);

@for(dayso(i):old_init_num(i+1)=old_init_num(i)
			-@sum(old(j):old_school(i,j))
			+@sum(new(j):new_school(i,j))
);
@for(sat(i):old_init_num(i+5)=old_init_num(5)
			-@sum(old(j):old_school(5,j))
			+@sum(new(j):new_school(5,j))
);
@for(sun(i):old_init_num(i+6)=old_init_num(6)
					-@sum(sat_old(j):old_school_sat(j))
					+@sum(sat_new(j):new_school_sat(j))
);
@for(mon(i):old_init_num(i+7)=old_init_num(7)
					-@sum(sun_old(j):old_school_sun(j))
					+@sum(sun_new(j):new_school_sun(j))
);
@for(mon(i):old_init_num(i+7)=old_init_num(1)
);
@for(newweek(i,j):
	@gin(new_school(i,j))
);
@for(oldweek(i,j):
	@gin(old_school(i,j))
);
@for(sat_new(i):
	@gin(new_school_sat(i));
);
@for(sat_old(i):
	@gin(old_school_sat(i));
);
@for(sun_new(i):
	@gin(new_school_sun(i));
);
@for(sun_old(i):
	@gin(old_school_sun(i));
);

最终解得：
校车运输空返问题
对于问题3，最少的空返数是49。

上一篇：Unix Socket


下一篇：Java -- JDBC学习笔记1、连接数据库添加数据